백준 9465 - 스티커

https://www.acmicpc.net/problem/9465

9465번: 스티커

score 배열에 각 스티커의 점수를 입력받는다.

j-1열까지의 스티커와 i행 j열 스티커를 확인했을 때 점수 합의 최댓값을 dp[i][j]라고 하자. dp[i][j]의 값은 다음과 같다.

 

1) j = 1

선택지가 하나밖에 없으므로 dp[i][1] = score[i][1]

2) j = 2

dp[i][2] = dp[1-i][1] + score[i][2] (i행 2열 스티커를 고를 경우)

                score[i][1] (i행 2열 스티커를 포기할 경우)

 

3) j >= 3

dp[i][j] = dp[1-i][j-1] + score[i][j]  (바로 왼쪽 위/아래 스티커를 고를 경우)

               dp[1-i][j-2] + score[i][j]  (바로  왼쪽 위/아래 스티커를 포기할 경우)

 

* score[i][j]를 반드시 골라야 하는 지 궁금할 수 있다. j = 2일 때처럼 score[i][j-1]이 더 클 경우 포기할 수도 있으니까. 하지만 score[i][j]를 고르지 않는 경우는 score[1-i][j]를 고르는 경우와 같다. 따라서 최종적으로 마지막 열의 두 값을 비교하면 원하는 답을 구할 수 있다.

 

느낀 점

dp는 푸는 것보다 증명하고 설명하는 게 더 어려운 듯