백준 1932: 정수 삼각형

Silver_I 난이도 문제를 C++로 풀이한 내용입니다. 정수 삼각형의 최상단에서부터 시작하여 아래로 내려오면서 각 숫자를 하나씩 선택하여 합이 최대가 되는 경로를 찾는 동적 계획법(Dynamic Programming) 문제입니다.

문제 소개

• 문제 번호: 1932
• 문제명: 정수 삼각형
• 난이도: Silver_I
• 사용 언어: C++
• 실행 시간: 36 ms
• 메모리: 3980 KB
• 문제 요약: 주어진 정수 삼각형에서 최상단의 숫자부터 시작하여 아래로 한 칸씩 이동하면서 숫자들을 더해 가장 큰 합을 만드는 경로를 찾는 문제입니다. 각 단계에서는 바로 아래 줄에 있는 왼쪽 또는 오른쪽 숫자로만 이동할 수 있습니다.

접근 방법

이 문제는 동적 계획법(Dynamic Programming)을 사용하여 해결할 수 있습니다. 삼각형의 각 칸으로 도달할 수 있는 최대 누적 합을 계산하고, 이를 바탕으로 최종적으로 삼각형의 가장 아래 줄에서 최대값을 찾으면 됩니다.

핵심 아이디어:
삼각형의 특정 위치 (i, j) (i는 행, j는 열)에 도달할 수 있는 최대 누적 합은, 해당 위치의 값과 그 위에서 올 수 있는 두 가지 경로 중 더 큰 값을 더한 것입니다. 즉, dp[i][j] = cost[i][j] + max(dp[i-1][j], dp[i-1][j-1]) 의 점화식을 사용합니다.

선택 이유:

1. 최적 부분 구조 (Optimal Substructure): 전체 문제의 최적 해가 부분 문제의 최적 해를 포함합니다. 즉, 가장 큰 합을 만드는 경로는 특정 칸까지 도달하는 가장 큰 합을 만드는 경로를 포함합니다.
2. 겹치는 부분 문제 (Overlapping Subproblems): 같은 부분 문제(특정 칸까지 도달하는 최대 누적 합)가 여러 번 계산될 수 있습니다. 동적 계획법은 이러한 중복 계산을 피하고 효율성을 높입니다.

풀이 과정

1. 입력 처리:

   • 먼저 삼각형의 크기 n을 입력받습니다.
   • 삼각형의 첫 번째 행(i=1)의 첫 번째 값(j=1)은 따로 입력받아 dp[1][1]에 저장합니다. 이 값은 경로의 시작점이 됩니다.

2. 동적 계획법 테이블 초기화 및 채우기:

   • dp[i][j] 테이블은 i행 j열에 도달하는 최대 누적 합을 저장합니다.
   • cost[i][j] 테이블은 해당 위치의 실제 숫자를 저장합니다.
   • i는 1부터 n까지, j는 1부터 i까지 반복합니다.
   • 첫 번째 행, 첫 번째 열(i=1, j=1)은 이미 초기값으로 설정되었으므로 건너뜁니다.
   • 각 (i, j)에 대해 해당 위치의 값 cost[i][j]를 입력받습니다.
   • dp[i][j]를 계산합니다. 이는 cost[i][j]와 위에서 올 수 있는 두 칸 dp[i-1][j] (바로 위)와 dp[i-1][j-1] (바로 위 왼쪽) 중 더 큰 값의 합입니다.
   • 경계 처리:
     • 삼각형의 왼쪽 끝 (j=1)에서는 위에서 바로 내려오는 dp[i-1][j] 경로만 가능합니다.
     • 삼각형의 오른쪽 끝 (j=i)에서는 위에서 왼쪽에서 오는 dp[i-1][j-1] 경로만 가능합니다.
     • 제공된 코드는 max(dp[i-1][j], dp[i-1][j-1]) 형태로 모든 경우를 처리합니다. dp 배열이 전역 변수로 0으로 초기화되어 있으므로, 경로가 존재하지 않는 경우 (예: dp[i-1][j-1]이 존재하지 않는데 j=1인 경우) max 함수에 0이 들어가게 되어 올바른 값이 처리됩니다.

3. 최대값 찾기:

   • 삼각형의 가장 아래 행 (n행)에 있는 모든 dp[n][k] 값들 중에서 최대값을 찾습니다. 이 값이 최종 결과가 됩니다.

주의할 점:

• 배열의 인덱스: 문제에서 1-based 인덱싱을 사용하는 경우, 코드에서도 1-based 인덱싱을 맞춰주어야 합니다. 제공된 코드는 1-based 인덱싱을 사용합니다.
• 경계 조건: 삼각형의 가장자리(왼쪽 끝, 오른쪽 끝)에서 올 수 있는 경로를 올바르게 처리해야 합니다.

코드 설명

#include<bits/stdc++.h>
using namespace std;
// dp[i][j]는 i, j까지의 최대 누적 비용
int dp[501][501];
int cost[501][501];

int main(){
    int n; cin >> n; // 삼각형의 크기(행의 수)를 입력받습니다.
    int first_cost; cin >> first_cost; // 첫 번째 행의 첫 번째 값(삼각형의 꼭대기)을 입력받습니다.
    dp[1][1] = first_cost; // dp 테이블의 초기값을 설정합니다.
    
    for(int i = 1; i <= n; i++){ // 각 행에 대해 반복합니다.
        for(int j = 1; j <= i; j++){ // 각 행의 열에 대해 반복합니다.
            if(i == 1 && j == 1) // 첫 번째 행의 첫 번째 값은 이미 처리했으므로 건너뜁니다.
                continue;
            
            cin >> cost[i][j]; // 현재 위치의 실제 비용(값)을 입력받습니다.
            // dp[i][j]를 계산합니다. 현재 비용 + 위에서 올 수 있는 두 경로 중 최대값
            // dp[i-1][j]는 바로 위에서 오는 경로, dp[i-1][j-1]는 위 왼쪽에서 오는 경로입니다.
            dp[i][j] = cost[i][j] + max(dp[i-1][j], dp[i-1][j-1]); 
            // 만약 왼쪽이나 오른쪽 끝이라 둘 중 하나의 dp 값만 존재하는 경우
            // dp 배열이 전역변수로 초기화되어 0으로 차있으므로 max 함수에 들어가면 정상 dp 값이 0보다는 클테니 문제 없이 처리된다.
        }
    }
    
    /*
        dp[1,1] = cost[1,1](7) // 첫 값은 대입
        ...
        dp[5,1] = cost[5,1](4) + min(dp[4,1](2), dp[3,1](x)) // 왼쪽 끝은 오른쪽 위에서만 내려올 수 있음
        ...
        dp[5,4] = cost[5,4](6) + min(dp[4,4](4), dp[4,3](4))
        dp[5,5] = cost[5,5](5) + min(dp[4,4](4), dp[4,5](x)) // 오른쪽 끝은 왼쪽 위에서만 내려올 수 있음
    
        dp[i][j] = cost[i][j] + min(dp[i-1][j], dp[i-1][j-1]); 라는 점화식을 가진다는 것을 관찰을 통해 알 수 있다
        => 위 주석의 'min'은 실수이며, 실제로는 'max'를 사용해야 합니다. 문제의 핵심은 최대합 경로이므로 더 큰 값을 선택해야 합니다.
    */
    
    int max_sum = 0; // 최대 누적 합을 저장할 변수
    for(int k = 1; k <= n; k++){ // 마지막 행(n행)의 모든 값들을 순회합니다.
        if(dp[n][k] > max_sum) // 현재 값이 지금까지 찾은 최대값보다 크면 갱신합니다.
            max_sum = dp[n][k];    
    }
    cout << max_sum; // 최종 최대 합을 출력합니다.
    return 0; // 프로그램 종료
}

복잡도 분석

• 시간 복잡도:

  • 삼각형의 총 숫자의 개수는 1 + 2 + ... + n = n(n+1)/2 입니다.
  • 각 숫자에 대해 상수 시간의 연산(입력, 덧셈, 최대값 비교)이 수행됩니다.
  • 따라서 시간 복잡도는 O(n^2) 입니다.

• 공간 복잡도:

  • dp 테이블과 cost 테이블은 각각 n x n 크기를 가집니다.
  • 따라서 공간 복잡도는 O(n^2) 입니다.

배운 점

• 동적 계획법(DP)의 기본 원리: 최적 부분 구조와 겹치는 부분 문제의 특성을 파악하여 DP를 적용하는 연습을 할 수 있었습니다.
• 삼각형 구조 문제 해결: 정수 삼각형과 같이 계단식 또는 삼각형 형태의 문제를 DP로 어떻게 모델링하는지 배울 수 있었습니다.
• 경계 조건의 중요성: DP 테이블을 채울 때, 특히 배열의 가장자리 부분에서 발생할 수 있는 예외적인 경우를 어떻게 처리해야 하는지 다시 한번 상기할 수 있었습니다. 제공된 코드는 전역 변수 초기화 값을 활용하여 경계 처리를 간결하게 구현한 점이 인상 깊었습니다.
• 주석의 활용: 코드 내 주석은 이해를 돕는 데 중요하며, 특히 과거의 잘못된 아이디어를 기록해두는 것도 도움이 될 수 있다는 것을 보여줍니다 (예: min에서 max로 수정된 부분).

이 문제를 통해 동적 계획법을 활용하여 효율적으로 최적의 경로를 찾는 방법을 익혔으며, 이는 다른 유사한 최적화 문제에도 적용될 수 있을 것입니다.