greentea31's Note

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

풀이 과정

위와 같은 정수 삼각형의 맨 위에서부터, 왼쪽 아래 혹은 오른쪽 아래 숫자를 더하면서 맨 아래까지 내려갈 때 만들 수 있는 최대 값을 구하는 문제이다.

위의 예시에서의 답은 7 + 3 + 8 + 7 + 5 = 30인데, 만약 그리디로 문제를 해결하려고 한다면 2번째 줄에서 3, 8 중에 8을 고르게 되어 답이 나오지 않는다.

DP로 풀어야 한다.

D[i][j]를 i번째 행의 j번째 열까지의 진행경로의 합이라고 하면 다음과 같은 점화식이 성립한다.

D[i][j] = max(D[i-1][j-1], D[i-1][j]) + A[i][j] (1 <= j <= i)

D[i][0] = D[i-1][0] + A[i][0]

D[i][i] = D[i-1][i-1] + A[i-1][i-1]

이를 통해 문제를 해결할 수 있다.

소스 코드

#include <iostream>
#include <algorithm>
using namespace std;

int d[501][501];
int a[501][501];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, input;
    cin >> n;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= i; j++) {
            cin >> input;
            a[i][j] = input;
        }
    }

    d[0][0] = a[0][0];

    for (int i = 1; i < n; i++) {
        for (int j = 0; j <= i; j++) {
            if (j == 0) {
                d[i][j] = d[i-1][j] + a[i][j];
            } else if (j == i) {
                d[i][j] = d[i-1][j-1] + a[i][j];
            } else {
                d[i][j] = max(d[i-1][j-1], d[i-1][j]) + a[i][j];
            }
        }
    }

    int maxValue = 0;

    for (int j = 0; j < n; j++) {
        if (maxValue < d[n-1][j]) maxValue = d[n-1][j];
    }

    cout << maxValue << '\n';

    return 0;
}

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

풀이 과정

정수 삼각형에 들어있는 요소를 담는 배열을 위의 그림과 같이 생각하면

d[i][0] = d[i-1][0] + p[i][0]

d[i][k] = max(d[i-1][k-1] + p[i][k], d[i-1][k] + p[i][k]) (1  <= k <= i-1)

d[i][i] = d[i-1][i-1] + p[i]

다음과 같은 점화식이 성립하고 이를 통해 문제를 해결하면 된다

소스 코드

import sys

n = int(sys.stdin.readline())
p = []
d = []

for i in range(n):
    p.append(list(map(int, sys.stdin.readline().split())))
    if i == 0:
        d.append([p[0][0]])
        continue
    d.append([d[i-1][0] + p[i][0]])
    for k in range(1, i):
        d[i].append(max(d[i - 1][k - 1], d[i - 1][k]) + p[i][k])
    d[i].append(d[i-1][i-1] + p[i][i])

print(max(d[n-1]))