Baekjoon 1932번 정수 삼각형

문제

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

걸린 시간

00 : 10 : 19

풀이

C++

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

int n;
int tri[500][500];
int cache[500][500];

int dp(int y, int x){
    // 기저 사례
    if(y == n-1)
        return tri[y][x];
    // 메모이제이션
    int& ret = cache[y][x];
    if(ret != -1)
        return ret;
    // 재귀 호출
    return ret = max(dp(y+1, x), dp(y+1, x+1))+tri[y][x];
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    for(int y = 0; y < n; y++)
        for(int x = 0; x < y+1; x++)
            cin >> tri[y][x];
    memset(cache, -1, sizeof(cache));
    cout << dp(0, 0) << "\n";
    return 0;
}

algospot TRIANGLEPATH 와 똑같은 기초 dp 문제이다. 트리 형태로 주어져 있어 top-down 방식으로 풀이했다.

다른 풀이

C++

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

int n;
int tri[500][500];
int cache2[2][500];

int dp2(){
    // n층의 값 초기화
    for(int x = 0; x < n; x++)
        cache2[(n+1)%2][x] = tri[n-1][x];
    // 반복 dp
    for(int y = n-2; y >= 0; y--)
        for(int x = 0; x <= y; x++)
            cache2[y%2][x] = max(cache2[(y+1)%2][x], cache2[(y+1)%2][x+1])+tri[y][x];
    return cache2[0][0];
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    for(int y = 0; y < n; y++)
        for(int x = 0; x < y+1; x++)
            cin >> tri[y][x];
    cout << dp2() << "\n";
    return 0;
}

복습할 겸 bottom-up & sliding window 으로도 풀이해보았다.