[백준/C++] 알고리즘 1932번 - 정수 삼각형

안녕하세요! 테크지니어22입니다.

오늘은 백준 알고리즘 1932번 - 정수 삼각형 울 풀어보도록 하겠습니다.

 

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

1932번: 정수 삼각형

 

[문제 접근]

제한시간은 2초이고, 완전탐색이 가능한지 확인을 했습니다. 처음에는 대략적으로 완전탐색이 어렵다고 판단이 들었습니다. 그래서 완전탐색을 목표로하는 BFS와 DFS의 접근방식을 고려하지 않았습니다. 엄밀히 계산해보면 n= 500일 때 모든 경로의 수는 2^499임을 알 수 있고 완전탐색으로 제한시간 2초이내로 실행하기 어렵다는 것을 알 수 있습니다. (그런데 어떤 분은 메모이제이션과 BFS를 이용해서 푸신 분도 있긴했습니다. 아마 메모이제이션을 아주 효율적으로 하여 확인해야할 경로를 줄였을 거라 판단합니다. 대단..)

그래서 저는 다이나믹 프로그래밍으로 접근하였습니다. 처음에 dp를 1차원적으로 정의를 내리려고 시도했으나 잘 되지 않았습니다.

그래서 2차원적으로 정의를 내렸습니다. 

dp[i][j]:  i층 j번째까지 합이 최대가 되는 경로에 있는 수의 합.

이렇게 정의를 하면 우리가 최대 경로에 있는 수의 합을 구하기 위해서 세 가지 분기만 따지면 됩니다.

1. 가장왼쪽경로

2. 가장 오른쪽 경로

3. 1,2를 제외한 경로들

이를 이용하여 풀이를 진행했습니다.

 

[풀이 전략]

1. 점화식의 초기값을 설정했습니다.

2- 1)가장 왼쪽 경로일 때는 dp[i][0] = dp[i-1][0] + arr[i][0]

2-2) 가장 오른쪽 경로일 때 dp[i][i] = dp[i-1][i-1] + arr[i][i];

2-3) 1,2를 제외한 경로일 때

만약  dp[i-1][j-1] > dp[i-1][j]이면 dp[i][j] = dp[i-1][j-1] + arr[i][j]

아니면 dp[i][j] = dp[i-1][j] + arr[i][j] 

로 업데이트 해줍니다.

3. i = 0 ~ i = n-1 까지 dp[n-1][i]를 확인하면서 가장 큰 값을 찾습니다.

4. 가장 큰 값을 출력합니다.

 

[코드]

#include <iostream>
#include <algorithm>
using namespace std;

// 정수 삼각형.

int n  ; 
int arr[501][501]; 
int dp[501][501]; // dp[i][j] i층 j번째까지 합이 최대가 되는 경로에 있는 수의 합
int maxCnt ;



int main() {
  ios::sync_with_stdio(0);
    cin.tie(0); 
    cin >> n ; 
    for(int i =  0 ; i < n ; i++)
        for(int j = 0 ; j <= i ; j++)
            cin >> arr[i][j];
    
        dp[0][0] = arr[0][0] ;
     dp[1][0] = dp[0][0] + arr[1][0]  ; 
     dp[1][1] = dp[0][0] + arr[1][1] ;
    for(int i =  2 ; i < n ; i++)
        for(int j = 0 ; j <= i ; j++){
            if(i== j) {
                dp[i][i] = dp[i-1][i-1] + arr[i][i];
            }
            else if(j == 0){
                dp[i][0] = dp[i-1][0] + arr[i][0]; 
            }

            else {
                if(dp[i-1][j-1] > dp[i-1][j]) dp[i][j] = dp[i-1][j-1] + arr[i][j];
                else dp[i][j] = dp[i-1][j] + arr[i][j];
        }
        }

    for(int i = 0 ; i < n ; i++){
        if(maxCnt < dp[n-1][i]) maxCnt = dp[n-1][i];
    }

    cout << maxCnt;
}

 

[배울 점]

- 1차원 다이나믹 정의가 어려우면 2차원 다이나믹 정의 생각해보기