Algorithm/DP

BOJ#9465 스티커

밤이2209 2016. 11. 24. 15:14

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) 구현하기





* 나의 코드

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





'Algorithm > DP' 카테고리의 다른 글

BOJ#11053 가장 긴 증가하는 부분 수열 (LIS)  (0) 2016.12.06
BOJ#2156 포도주 시식  (0) 2016.11.25
BOJ#10844 쉬운 계단 수  (0) 2016.11.22
BOJ#11726 2xn 타일링  (0) 2016.11.21
BOJ#1463 1로 만들기  (0) 2016.11.21