알고리즘 문제해결 전략 Chapter 08 - TRIANGLEPATH(C++)

예제: 삼각형 위의 최대 경로

문제

6
1  2
3  7  4
9  4  1  7
2  7  5  9  4

위 형태와 같이 삼각형 모양으로 배치된 자연수들이 있습니다. 맨 위의 숫자에서 시작해, 한 번에 한 칸씩 아래로 내려가 맨 아래 줄로 내려가는 경로를 만들려고 합니다. 경로는 아래 줄로 내려갈 때마다 바로 아래 숫자, 혹은 오른쪽 아래 숫자로 내려갈 수 있습니다. 이 때 모든 경로 중 포함된 숫자의 최대 합을 찾는 프로그램을 작성하세요.

입력
입력의 첫 줄에는 테스트 케이스의 수 C(C <= 50)가 주어집니다. 각 테스트 케이스의 첫 줄에는 삼각형의 크기 n(2 <= n <= 100)이 주어지고, 그 후 n줄에는 각 1개~n개의 숫자로 삼각형 각 가로줄에 있는 숫자가 왼쪽부터 주어집니다. 각 숫자는 1 이상 100000 이하의 자연수입니다.

출력
각 테스트 케이스마다 한 줄에 최대 경로의 숫자 합을 출력합니다.

예제 입력

2
5
6
1  2
3  7  4
9  4  1  7
2  7  5  9  4
5
1 
2 4
8 16 8
32 64 32 64
128 256 128 256 128

예제 출력

28
341

풀이

필자가 이전에 풀었던 TRIPATHCNT의 쉬운 버전 문제쯤 될 것 같다. 순서가 이렇게 된 이유는 책 초반으로 다시 돌아갔기 때문이다. 기초가 모자라.. 나중에 TRIPATHCNT도 다시 풀 예정이 기대하시라.

역시나 동적계획법 문제인데, 삼각형의 아래 두 개의 값을 가져와서 더 큰값으로 cache에 저장하면 되겠다.

전체적인 소스코드는 아래와 같다.

소스 코드

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

int n;
int tri[100][100];
int cache[100][100];

int biggestSum(int y, int x) {
	//기저 : 삼각형 끝에 다다랐을 때
	if (y == n - 1) return tri[y][x];

	int& res = cache[y][x];
	if (res != -1) return res;

	res = tri[y][x] + max(biggestSum(y + 1, x), biggestSum(y + 1, x + 1));

	return res;
}

int main() {

	int testCase;
	cin >> testCase;

	for (int tc = 0; tc < testCase; tc++) {
		memset(cache, -1, sizeof(cache));
		cin >> n;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j <= i; j++) {
				cin >> tri[i][j];
			}
		}

		cout << biggestSum(0, 0) << endl;
	}

	return 0;
}

풀이 후기

그래도 계속 동적계획법 문제를 풀다보니, 난이도 하 문제들은 조금씩 눈에 익는다.
이렇게 말해놓고 다른 유형이 나오면 또 한세월 걸리겠지만, 익숙해지면 익숙해질수록 비슷한 유형의 문제는 금방금방 풀어내는 것 같다. 많이풀자!