(파이썬 python) 백준 9465번 : 스티커

# 9465번 : 스티커

t = int(input())
for _ in range(t):
    n = int(input())
    dp = [list(map(int,input().split())),list(map(int,input().split()))]
    
    for i in range(1,n):
        if i == 1:        
            dp[0][i] += dp[1][i-1]
            dp[1][i] += dp[0][i-1]
        else:
            dp[0][i] += max(dp[1][i-1], dp[1][i-2])
            dp[1][i] += max(dp[0][i-1], dp[0][i-2])
    print(max(dp[0][n-1],dp[1][n-1]))

 

 

 

총 세가지 케이스로 나눠서 생각해 볼 수 있다.

 

1) n == 1인 경우

제일 쉬운 케이스이다. 아래의 그림처럼 두개의 수 중 큰 수를 출력해주면 된다. 

2) n == 2인 경우

이 경우도 쉬운 케이스로 양 대각선 조합의 수 중 합이 큰 숫자를 출력해주면 된다.

아래의 경우는 50+50 > 30+10 이므로 100을 출력해주면 됨 

그리고 아래 그림과 같이 n=2까지의 최대값의 결과를 뒤의 문제에서도 사용하기 위해서 최대값을 대입해준다.

 

3) n > 2인 경우

이제부터는 최대값을 구하기 위해서 두가지 경우의 수를 비교해보고 큰 값을 취해야 한다.

1. dp[1][i-1] or dp[0][i-1] - 직전 대각선 방향의 숫자가 최대인 경우
2. dp[1][i-2] or dp[0][i-2] - 전전 대각선 방향의 숫자가 최대인 경우

이렇게 최대값을 구하고 마지막 열의 2개의 수중 최대값을 출력하면 된다.