BOJ : 1932 정수 삼각형

 

 

---

[BOJ 1932(S1) 리뷰]

DP문제다. 역시 DP문제는 너무 어렵다.

삼각형 위에서 아래로 내려가며 가장 큰 최대값을 찾는 문제이다.

내려갈땐 대각선 왼쪽, 대각선 오른쪽에 위치한 값으로만 내려갈 수 있다.

크기가 작다면 완전탐색으로도 가능했을테지만, 이 문제는 DP를 이용하지않으면 시간초과를 맞게 된다.

 

각 위치마다 할 수 있는 선택은 왼쪽으로 가냐 오른쪽으로 가냐이다.

당연히 우리는 두개의 방향 중 끝까지 내려갔을때 최대값이 되는 방향으로 가야 한다.

그러나 우리는 미래를 내다볼 수 없으므로 현재의 위치에서 바로 왼쪽으로 갈지 오른쪽으로 갈지 결정할 수가 없다.

따라서 아래쪽 삼각형부터 값을 확인하며 위로 올라가는 방법을 택했다.

 

DP배열을 통해 각 삼각형의 위치마다, 아래에서 위로 올라올때마다의 최대값을 저장해 주었다.

발퀄 ㅈㅅ..

맨 아래 삼각형부터 보면된다. 가장 바닥에 있는 값중 최대값과 자신의 값을 더해 DP배열에 저장하는 과정을 위로 올라가면서 계속 최대값에 대해 더해주면 된다. 코드로 보는게 이해가 빠를것이다.

 

 

 

---

#include <bits/stdc++.h>
using namespace std;

int arr[501][501];
int N;
int dp[501][501];
int f(int d,int c) //d는 깊이,c는 위치
{
    if (d == N) return arr[d][c];
    if (dp[d][c]) return dp[d][c];
    return dp[d][c]=max(f(d + 1,c), f(d + 1,c + 1))+arr[d][c];
}
int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    

    cin >> N;
    
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= i; j++)
        {
            cin >> arr[i][j];
        }
    }

    cout << f(1, 1);


}