[백준] 1932번 정수 삼각형 (C++) - dynamic programming

문제

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

1932번: 정수 삼각형

코드

#include <iostream>

using namespace std;

int dp[500][500];

int main(){
  int n;
  cin >> n;
  for(int i=0; i<n; i++){
    for(int j=0; j<=i; j++){
      cin >> dp[i][j];
    }
  }
  for(int i=1; i<n; i++){
    for(int j=0; j<=i; j++){
      if(j==0) dp[i][j] = dp[i-1][0]+dp[i][j];
      else if(j==i) dp[i][j] = dp[i-1][j-1]+dp[i][j];
      else dp[i][j] = max(dp[i-1][j-1], dp[i-1][j])+dp[i][j];
    }
  }
  int maxNum = 0;
  for(int i=0; i<n; i++){
    if(dp[n-1][i]>maxNum) maxNum = dp[n-1][i];
  }
  cout << maxNum;
  return 0;
}

정리

dp를 이용해 규칙을 찾으면 되는 문제이다.

        7
      3   8
    8   1   0
  2   7   4   4

각 층의 숫자마다 그 시점에서 최댓값을 찾아보자.

1층은 그 자신이 최댓값이므로 생략하고 2층부터 보자

 

2층

1층	     7
2층	  10  15
3층
4층

dp[1][0] = dp[1][0]+dp[0][0] (3+7=10)

dp[1][1] = dp[1][1]+dp[0][0] (8+7=10)

 

3층

1층	     7
2층	  10  15
3층	18  16  15
4층

dp[2][0] = dp[2][0]+dp[1][0] (8+10=18)

dp[2][1] = dp[2][1]+max(dp[1][0], dp[1][1]) (1+15=16)

dp[2][2] = dp[2][2]+dp[1][1] (0+10=10)

 

4층

1층	       7
2층	    10  15
3층	  18  16  15
4층     20  25  20  19

dp[3][0] = dp[3][0]+dp[2][0] (2+18=20)

dp[3][1] = dp[3][1]+max(dp[2][0], dp[2][1]) (7+18=25)

dp[3][2] = dp[3][2]+max(dp[2][1], dp[2][2]) (4+16=20)

dp[3][3] = dp[3][3]+dp[2][2] (4+15=19)

 

이것들을 일반화하면 다음과 같이 나타낼 수 있다. (i는 층, j는 층 내의 순서)

j==0일때(층 내에서 첫번째 순서일때)     dp[i][j] = dp[i][j]+dp[i-1][0]     (i>1)

j==i일때(층 내에서 마지막 순서일때)      dp[i][j] = dp[i][j]+dp[i-1][j-1]      

else       dp[i][j] = dp[i][j]+max(dp[i-1][j-1], dp[i-1][j]) 

참조

https://gaeunhan.tistory.com/67