BOJ#9465 스티커

BOJ#9465 스티커

* 문제

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

* 풀이

동적계획법(Dynamic Programming) 문제입니다.

최종적으로 점화식을 구해야 문제를 풀 수 있습니다.

0) 자료구조

- 각 스티커의 점수를 저장하는 2차원 int 배열 : cost

- 0열에서 출발하여 해당 위치까지의 점수의 합을 저장하는 2차원 int 배열 : dp

1) 시작점 생각하기

0열에서 시작한다고 생각해봅시다. 시작점은 (0, 0), (0, 1)으로 2개가 됩니다.

2) 다음 스티커 선택하기

(0, 0)에서 시작할 경우 (1, 1), (1, 2) 스티커를 선택할 수 있습니다. 

그리고 (1, 1)과 (1, 2) 중에서 큰 값을 선택하면 됩니다.

한편, (0, 0)에서 (0, 2), (1, 3) 등을 선택하는 경우는 고려할 필요가 없습니다.

왜냐하면 아래 그림에서 볼 수 있는 것처럼, 파란색 경로로 이동하는 것이 더 점수의 합이 크기 때문입니다.

결국, 다음 스티커는 현재 스티커의 대각선 스티커 2개 중에 큰 점수의 스티커를 선택하면 됩니다.

3) 점화식 생각하기

따라서, 점화식은 아래와 같이 세울 수 있습니다.

dp[0][N] = Max(dp[1][N-1], dp[1][N-2]) + cost[0][N]

dp[1][N] = Max(dp[0][N-1], dp[0][N-2]) + cost[1][N]

4) 구현하기

for (int i = 1; i <= n; i++) { dp[0][i] = Math.max(getDPValue(1, i - 1), getDPValue(1, i - 2)) + cost[0][i]; dp[1][i] = Math.max(getDPValue(0, i - 1), getDPValue(0, i - 2)) + cost[1][i]; } System.out.println(Math.max(getDPValue(0, n), getDPValue(1, n)));

---

* 나의 코드

https://github.com/stack07142/BOJ/tree/master/BOJ%239465_Sticker