2024/12/27 금 매일백준

오늘의 문제는

1932번: 정수 삼각형

이다.

문제이다.

가장 큰 값을 가지는 루트의 합을 출력하면 되는 문제.

저번 문제인가 ? 그 색칠하는 문제랑 비슷한 것 같다.

현재 값 + 이전 단계의 최대값 이었던 것 같은데 여튼 비슷한 느낌이다.

올바르게 값이 출력되는데 정의를 하지 않아서 그런가 계속 틀려서 시간 초과나 그런 문제인줄 알고 식겁햇다.

이제 대부분의 DP 브론즈, 실버 문제들은 비슷한 방식으로 풀리는 것 같다.

코드는 아래와 같다.

#include <iostream>
#include <algorithm>

using namespace std;

int main(void) {

    int n, tri[501][501] = {0}, DP[501][501] = {0}, res = -1;

    cin >> n;

    for(int i=1;i<=n;i++) {
        for(int j=1;j<=i;j++) {
            cin >> tri[i][j];
        }
    }
    DP[1][1] = tri[1][1];
    for(int i=2;i<=n;i++) {
        for(int j=1;j<=i;j++) {
            DP[i][j] = max(DP[i-1][j-1], DP[i-1][j]) + tri[i][j];
        }
    }

    for(int i=1;i<=n;i++) {
        res = max(res, DP[n][i]);
    }

    cout << res << endl;

    return 0;
}

위 코드는 상위 단계에서 아래로 진행하는 구조이고, 반대로 하위 단계에서 위로 진행하도록 코드를 짜도 무방하다. 정의를 하지 않아서 코드 정답은 통과를 못받았지만, 정상적으로 값이 출력되므로 아래에 올리기는 하겠다.

#include <iostream>
#include <algorithm>

using namespace std;

int main(void) {

    int n, tri[501][501];

    cin >> n;
    
    // input
    for(int i=1;i<=n;i++) { 
        for(int j=1;j<=i;j++) {
            cin >> tri[i][j];
        }
    }

    for(int i=n-1;i>=0;i--) {
        for(int j=1;j<=i+1;j++) {
            tri[i][j] = max(tri[i+1][j], tri[i+1][j+1]) + tri[i][j];
        }
    }

    cout << tri[0][1] << endl;

    return 0;
}

아래에서 위로 진행하는 코드가 추후에 어떤 값이 제일 큰지 비교할 필요가 없어서 더 간단한 듯 하다. 아래에서 위로 올라올수록 배열의 개수가 줄기 때문에 자연스럽게 하나로 모아지기 때문이다. ^^

끝. 올해의 한 해가 얼마 남지 않았고, 나의 군입대도 얼마 남지 않았다. 건강하게 열심히 살아보자. 2024년 화이팅.