9465 - 스티커

1) 문제 설명

- 스티커를 선택하는데 최대 점수로 선택했을 때 점수를 출력!

-

- 위 그림에서는 점수가 50, 50, 100, 60인 스티커를 고르면, 점수는 260이 되고 이 것이 최대 점수이다. 

 

2) 문제 아이디어

- DP로 풀수 있으며, 선택의 문제이다. 

- 점수를 규칙대로 채우면 마지막 값만 비교하면 된다. 

 

처음에는 기본 값을 넣어준다

2번째 항에는 1번째 항의 결과값과 조건으로 주어진 점수표를 더해서 넣으면 된다. 

단, 인접항 항은 더할 수 없으므로 대각선으로만 더해서 나간다. 

예를 들면 dp[0][1]에 올수 있는건 dp[1][0] + 첫번째라인[1] 이다

문제에서 보면 3번째 열 이후에는 한번 선택을 하지 않는다. 그림으로 설명해보면, 4번째 열에서는 일부러 선택을 안한다. 

왜냐하면 마지막에서 60이라는 수를 선택하기 위해서 일부러 건너뛴것이다. 

 

이걸 어떻게 프로그래밍 해야할까? 

선택한 방법은 max함수를 사용해서 비교해보는 것이다. 

max(dp[i][j] , dp[i][j-2] + 첫번째라인[1]) 이런식으로 설계를 하는것이다.

 

제일 어려웠던 것은 i,j의 배열에서 자꾸 헷갈린다..._--

 

아마 다들 코드 보면 쉽게 이해를 할 것이다.

import sys

t = int(input())
for _ in range(t):
    n = int(input())

    first_lst = list(map(int, sys.stdin.readline().split()))
    second_lst = list(map(int, sys.stdin.readline().split()))

    dp = [[0 for _ in range(n)] for _ in range(2)]

    dp[0][0] = first_lst[0]
    dp[1][0] = second_lst[0]

    for j in range(1, n):
        for i in range(2):
            if i == 0:
                dp[i][j] = dp[i+1][j-1] + first_lst[j]
                if j>1:
                    dp[i][j] = max(dp[i][j], max(dp[i][j-2], dp[i+1][j-2])+ first_lst[j])
            else:
                dp[i][j] = dp[i-1][j-1] + second_lst[j]
                if j>1:
                    dp[i][j] = max(dp[i][j], max(dp[i][j-2], dp[i-1][j-2])+ second_lst[j])

    print(max(dp[0][n-1], dp[1][n-1]))