1932번: 정수 삼각형(백준 C++)

1932번: 정수 삼각형 링크

코드

#include <iostream>
using namespace std;

int n;
int tri[500][500];

void init(){
  cin >> n;
  for(int i=0; i<n; i++){
    for(int j=0; j<=i; j++){
      cin >> tri[i][j];
    }
  }
}

void solve(){
  int max_num = 0;
  for(int i=1; i<n; i++){
    for(int j=0; j<n; j++){
      if(j == 0) tri[i][j] += tri[i-1][0];
      else if(j == i) tri[i][j] += tri[i-1][i-1];
      else tri[i][j] += tri[i-1][j-1] > tri[i-1][j] ? tri[i-1][j-1] : tri[i-1][j];

      if(tri[i][j] > max_num) max_num = tri[i][j];
    }
  }
  cout << max_num;
}
int main(){
  init();
  solve();
}

풀이 및 사견

기본적으로 어제 풀었던 'RGB거리 문제 풀이' 와 동일하다.
Dynamic Programing 중 하나.

문제

          7
       3    8
     8    1    0
   2   7    4   4
 4   5   2    6   5

위에서 부터 아래로 내려오면서 거치는 수를 모두 합 했을때 마지막 합이 가장 크게 될 때의 수를 찾는 문제이다.
단, 내려올 때 선택할 수 있는 선택지는 왼, 오른쪽 대각선 2가지이다.

---

점화식

(N-1)층까지 수의 합의 최대값 + N층의 수

N층의 각 수에 대해서, 각 수가 N-1층에서 선택할 수 있는 수 중 최대값을 선택하면 된다.

• 초기값 (N = 1)

          7
       3    8
     8    1    0
   2   7    4   4
 4   5   2    6   5

• N = 2
  2층의 수 3, 8은 선택지가 1층의 7밖에없다. 더해준다.

          7
      10   15
     8   1    0
   2   7    4   4
 4   5   2    6   5

N = 2 인경우 최대값은 15가 된다.

• N = 3
  3층의 수 8, 1, 0 중
  8은 선택지가 10밖에 없다. (왼쪽 위 대각선이 없기 때문)
  1은 선택지가 10과 15가 있다. 이 중 15가 더 큰 수이므로 15와 더해준다.
  0은 선택지가 15밖에 없다. (오른쪽 위 대각선이 없기 때문)

           7
       10   15
    18   16    15
   2   7    4    4
 4   5   2     6    5

N = 3 인경우 최대값은 18가 된다.

• N = 4
  N = 3과 동일한 방식으로 해준다.
  즉, 각 층의 맨 왼쪽의 수는 이전층의 맨 왼쪽수와만 더해지며
  맨 오른쪽의 수는 이전층의 맨 오른쪽수와 더한다.
  이외의 수들은 두 대각선에 있는 수 중 큰 수를 찾아 더해준다.

            7
        10   15
     18    16    15
   20   25   20   19
 4    5     2     6     5

N = 4 인경우 최대값은 25가 된다.

• N = 5

            7
        10   15
     18    16    15
   20   25   20   19
 24   30   27   26   24

N = 5 인경우 최대값은 30가 된다.

변수

int tri[500][500];

삼각형의 각 층의 수를 담는 배열을 선언해준다.
편의상 2차원배열로 했지만
어차피 각 층에 몇 개의 수가 있는지는 정해져 있으므로
1차원 배열을 해도 무방할 듯 하다.

풀이

void solve(int n){
    for(int i=1; i<n; i++){
        for(int j=0; j<3; j++){
            if(rgb[i-1][(j+1) % 3] < rgb[i-1][(j+2) % 3]){
                rgb[i][j] += rgb[i-1][(j+1) % 3];
            }
            else{
                rgb[i][j] += rgb[i-1][(j+2) % 3];
            }
        }
    }
    int min = 1000001;
    for(int k=0; k<3; k++){
        if( rgb[n-1][k] < min ) min = rgb[n-1][k];
    }
    cout << min;
}

이중 반복문을 N층의 각 수에대한 최대값을 구하게 된다.
i는 N(층)을 나타내는 변수
j는 각 층의 수를 나타내는 변수

RGB거리 문제라던지, 우선 DP 문제 하나를 제대로 풀고 찾아보면서 감을 익히면
수월하게 풀 수 있는 난이도의 문제인 것 같다.
같은 풀이방법으로 풀 수 있는 문제이기 때문이다.