[기출 상] 주울 수 있는 최대의 돈2(정수삼각형)

[문제]

주울 수 있는 최대의 돈 문제와 같은 조건이되, 삼각형으로 돈이 위치한 경우이다. 아래층으로 내려갈 때는 바로 아래 또는 오른쪽 대각선 아래로만 이동 가능하다.

예를 들어, 

1

5 2

2 3 4

5 4 9 2

4 7 1 7 3

으로 돈이 놓여있다면 최대값은 25이다.

 

[풀이]

동적프로그래밍을 이용하여 풀면된다. 고려해야 할 경우는 3가지인데, 아래로만 이동하는 경우, 오른쪽 대각선으로만 이동하는 경우, 그 중간 부분이 있다.

아래로만 이동하는 경우 money[i][j] = money[i][j] + money[i-1][j].

오른쪽 대각선으로만 이동하는 경우 money[i][j] = money[i][j] + money[i-1][j-1].

가운데 부분의 경우 money[i][j] = money[i][j] + max(money[i-1][j], money[i-1][j-1]).

 

[코드]

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

long long MAX(long long x, long long y){
	return (x > y) ? x : y;
}

long long solution(int N, vector<vector<long long>> money) {
	//아래쪽, 오른쪽 대각선 중 하나를 선택. 총합이 최대가 되는.
	
	for(int i=1; i<N; i++){
		for(int j=0; j<=i; j++){
			if(j==0)
				money[i][j] += money[i-1][j] ;
			else if(j==i)
				money[i][j] += money[i-1][j-1];
			else{
				money[i][j] += MAX(money[i-1][j-1], money[i-1][j]);
			}
		}
	}
	
	long long m = -1;
	for(int i=0; i<N; i++){
		if(money[N-1][i] > m)
			m = money[N-1][i];
	}
	
	return m;
	
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int N;
    cin >> N;

    vector<vector<long long>> money;
    for (int i = 0; i < N; i++) {
        money.push_back(vector<long long>(i + 1, 0));
        for (int j = 0; j <= i; j++) {
            cin >> money[i][j];
        }
    }
    cout << solution(N, money) << "\n";
    return 0;
}