3. 백준 1932 숫자삼각형 문제 공부

1. 문제를 풀면서

 백준 온라인 저지에서 푼 문제를 내 블로그에 다루려고 한다. '동적 계획법 기초 단계'의 세 번째 문제이다. 동적 계획법을 이런 방식으로 사용하는구나 하고 느낄 수 있다.

2. 문제 출처 및 보기

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

3. 문제 해결

 숫자 삼각형은 아래와 같다. 

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

 7은 이전 값이 없으므로 3부터 문제를 해결해 나갈 수 있다. 두 번째 줄부터 모든 수는 왼쪽 위 또는 오른쪽 위 수와 더해서 너 높은 값을 만들어 나갈 수 있는데, 왼쪽 경사에 있는 3같은 경우에는 왼쪽 위에 수가 없으므로 오른쪽 위의 수를 더한다(오른 쪽도 마찬가지..). 이런 방식으로 맨 마지막 줄까지 계산을 완료했다면 이제까지 선택된 수의 합이 최대가 되는 경로를 구할 수 있을 것이다. 

 데이터 구조는 vector를 이용했으며, 1차원 형태이다.

 

4. 소스코드

#include <iostream>
#include <algorithm>
#include <vector>
 
using namespace std;
 
int main()
{
    int N, len, maxVal = 0, answer = 0;
    vector<int> score, dp;
 
    // 데이터 입력
    scanf("%d", &N);
    len = N*(1 + N) / 2;
    score.push_back(0);
    dp.push_back(0);
    for (int idx = 1; idx <= len; idx++) {
        int val;
        scanf("%d", &val);
        score.push_back(val);
    }
 
    // 문제 해결 
    dp = score; // dp의 데이터 공간(+index)을 score와 같게 만들기 위한 임시 초기화
    for (int n = 2; n <= N; n++) {
        for (int idx = 0; idx < n; idx++) {
            int l_sum = 0, r_sum = 0;
            l_sum = r_sum = score[(n - 1)*n / 2 + 1 + idx];
            if (idx > 0)
                l_sum += dp[(n - 1)*n / 2 + 1 + idx - n];
            if (idx < n - 1)
                r_sum += dp[(n - 1)*n / 2 + 1 + idx - n + 1];
            dp[(n - 1)*n / 2 + 1 + idx] = max(l_sum, r_sum);
            answer = max(answer, max(l_sum, r_sum));
        }
    }
 
    // 결과 출력
    printf("%d\n", answer);
    return 0;
}