티스토리 뷰
https://www.acmicpc.net/problem/1932
[ 문제 풀이 법 ]
다이나믹 프로그래밍은 bottom-up방식으로 밑에서 위로 올라가는 방식이다. 분할정복법과 대조된다.
문제풀이법을 살펴보자. 임의의 원소까지의 최대값은 어떻게 될까? 위 예제에서 3행 2열의 값인 1을 임의의 원소로 잡고 여기까지의 최대값은 무엇일까? 최대값을 배열 DP에 저장한다.
아마 대답을 이렇게 미룰 수 있을 것이다. 3행 2열을 오기 바로 전의 최대값 + 3행 2열의 값.
의문은 3행 2열 바로 전까지의 최대값을 바로 알 수 가없다. 그런데, (1, 1)부터 시작하면, 최대값을 하나씩 쌓아갈 수 있다. 그래서 다이나믹 프로그래밍이 bottom-up방식의 문제해결법인 것이다.
3행 2열 바로 전까지의 최대값의 후보는 2행 1열의 값(3)과 2행 2열의 값(8)이다. 이 두 값을 비교해서 큰 값을 선택한다. 나는 코드에서 left와 right라는 변수로 표현했다.
[ Code ]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 | #include<stdio.h> #define MAX 501 int N; int Tri[MAX][MAX], DP[MAX][MAX]; void InData() { scanf ( "%d" , &N); for ( int i = 1; i <= N; i++) for ( int j = 1; j <= i; j++) scanf ( "%d" , &Tri[i][j]); } int main() { InData(); DP[1][1] = Tri[1][1]; int max = DP[1][1]; for ( int i = 1; i <= N; i++) { for ( int j = 1; j <= i; j++) { int left = DP[i - 1][j - 1]; int right = DP[i - 1][j]; if (left > right) DP[i][j] = left + Tri[i][j]; else DP[i][j] = right + Tri[i][j]; if (DP[i][j] > max) max = DP[i][j]; } } printf ( "%d\n" , max); return 0; } |
'알고리즘 > 다이나믹 프로그래밍' 카테고리의 다른 글
백준_동전1 (0) | 2016.07.29 |
---|