# 백준 : 숫자삼각형(1932)

문제

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

소스

(Github: https://github.com/wonjnlee/wallydev/blob/master/bj_1932_numbertriangle)

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cstring>
#include <list>
using namespace std;

int map[501][501];
int dp[501][501];
int size;

int main(void) {
    int value   = 0;
    int result  = 0;
    int maximum = 0;
    
    cin>>size;
    
    for(int i=0; i<size; i++) {
        for(int j=0; j<=i; j++) {
            cin>>value;
            map[i][j] = value;
        }
    }

    dp[0][0] = map[0][0];
    for(int i=1; i<=size; i++)
    {
        for(int j=0; j<=i; j++)
        {
            // 오른쪽 대각선 위를 더함
            if(j <= i - 1) {
                result = map[i][j] + dp[i - 1][j];
                if(dp[i][j] < result)   dp[i][j] = result;
                if(maximum < dp[i][j])  maximum = dp[i][j];
            }
            // 왼쪽 대각선 위를 더함
            if(j > 0) {
                result = map[i][j] + dp[i - 1][j - 1];
                if(dp[i][j] < result)   dp[i][j] = result;
                if(maximum < dp[i][j])  maximum = dp[i][j];
            }
        }
    }
    cout<<maximum<<endl;
    return 0;
}

풀이

오늘부터 DP(Dynamic Programming, 동적 계획법이라고도 한다)를 공부해보려고 한다. 사실 DP하면 두려움부터 앞선다. 그 점화식을 상상해내는 것이 굉장히 어렵고 까다롭기 때문인데(다르게 표현하면, 점화식만 상상해내면 식은 완전 쉽게 짤 수 있다는 말이 된다), 무튼 DP도 알고리즘이고 연습이 중요한 실력향상의 지름길이니까. 무튼 그렇다.
대부분의 DP는 bottom-up 방식으로 동작한다. 이 말은 '위의 결과를 참조하여 아래(현재점)에서의 결과를 도출해낸다'는 말이다. 그래서 나도 처음 시작점을 기준으로 그 아랫칸부터 마지막 칸까지의 결과값을 계산하였다.

무튼 위와 같은 순서로 계산이 이루어지는데, 각 상황별로 왼쪽 대각선과 오른쪽 대각선을 계산해서 큰 값을 DP 행렬에 넣어주면 된다. 참고로 만들어진 삼각형을 모두 왼쪽으로 밀어넣어서 행렬로 만들었을 때, 왼쪽 대각선은 바로 윗칸에서 왼쪽 옆이 되고, 오른쪽 대각선은 바로 윗칸이 된다. 
그렇게 해서 쭉쭉 계산하면 성공! 이 문제 풀고 DP에 자신감이 생겼다!