[백준 BOJ][DP] 1932 정수 삼각형

1932_정수 삼각형

 

링크

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

 

풀이

 

 

 

우선 어떤 정수로 올 수 있는 방법을 알아봅시다.

양 끝 대각선에 있는 정수로 올 수 있는 방법은 단 한 가지입니다.

 

 

이렇게 말이죠.

 

그럼 양 끝 대각선에 있는 정수가 아닌 경우에는 어떤 방법이 있을까요?

 

 

어떤 정수를 잡던지 방법은 왼쪽 위와 오른쪽 위 두 가지 방법이 있을 것입니다.

 

그렇다면 어떠한 정수로 오는 경로의 합의 최댓값을 구해줘서 저장해 놓으면 되겠네요.

그림으로 설명하겠습니다.

 

 

이렇게 두 선택지 중 더 큰 쪽에서 오는 걸로 선택해 더해주면 됩니다.

 

삼각형의 크기 n은 1 <= n <= 500이니, DP[501][501] 배열을 만들어 줍니다.

1~n까지 입력을 받고, i는 2부터 n까지, j는 1부터 n까지 for문을 돌려줍니다.

j가 1이면 DP[i][j] += DP[i-1][j]를 해줍니다.

j가 n이면 DP[i][j] += DP[i-1][j-1]을 해줍니다.

나머지 경우(else)라면 DP[i][j] += MAX(DP[i-1][j-1], DP[i-1][j])를 해줍니다.

 

마지막 n번째 줄에서 최댓값을 구해서 출력해줍니다.

 

코드

 

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

//1932_정수 삼각형 #include <cstdio> using namespace std;   int DP[501][501];   int MAX(int a, int b) {     return a > b ? a : b; }   int main() {     int i, j;     int n, max = -1;       scanf("%d", &n);       for (i = 1; i <= n; ++i) {        //입력 받음         for (j = 1; j <= i; ++j) {             scanf("%d", &DP[i][j]);         }     }       for (i = 2; i <= n; ++i) {         for (j = 1; j <= i; ++j) {             if (j == 1) DP[i][j] += DP[i - 1][j];            //한 가지 경로             else if (j == n) DP[i][j] += DP[i - 1][j - 1];    //한 가지 경로             else DP[i][j] += MAX(DP[i - 1][j], DP[i - 1][j - 1]);    //두 가지 경로 중 큰 값에서 내려오는 경로         }     }       for (i = 1; i <= n; ++i) {            //n줄의 max 값을 저장         max = MAX(max, DP[n][i]);     }       printf("%d", max);                    //max 출력       return 0; } Colored by Color Scripter

cs