[알고리즘 스터디] 알고스팟 #TRIANGLEPATH

[문제]

삼각형 모양으로 배치된 수들이 있다.

이 수들에 대해서 위에서부터 아래로 내려오는 경로를 만드려고 한다.

아래 줄로 내려갈 때 마다, 바로 아랫칸이나 한칸 오른쪽 아래칸으로 내려갈 수 있다.

지나온 경로상의 모든 수의 합의 최댓값을 구해라. 

 

[Input]

C (testcase 수)

각 testcase마다 

n (층의 개수)

n줄에 걸쳐 삼각형 각 가로줄에 있는 숫자 입력 

 

[Output]

각 testcase마다 최대 경로 숫자의 합

 

[풀이]

 

알고리즘은 위와 같다. dynamic programming을 사용하면, 모든 경로를 하나씩 살펴보지 않고, 바로 위에 칸과의 경우의수만 계산해주면 되기 때문에 복잡도를 크게 줄일 수 있다.

이 알고리즘의 복잡도는 O(n^2)이다. 

 

좀 더 큰 input의 예시를 살펴보면

이런 결과가 나온다.

 

[코드]

 

#include <stdio.h>
#include <iostream>
#include <algorithm>

using namespace std;
int main() {
	int C,n;
	int triangle[101][101];
	int cache[101][101];
	scanf_s("%d", &C);
	for (int i = 0;i < C;i++) {
		scanf_s("%d", &n);
		for (int j = 0;j < n;j++) {
			for (int k = 0;k <= j;k++) {
				scanf_s("%d", &triangle[j][k]);
			}
		}
		cache[0][0] = triangle[0][0];
		int maxSum;
		for (int j = 1;j < n;j++) {
			maxSum = cache[j - 1][0];
			cache[j][0] = triangle[j][0] + maxSum;
			for (int k = 1;k <= j;k++) {
				maxSum = (cache[j - 1][k] > cache[j - 1][k - 1]) ? cache[j - 1][k] : cache[j - 1][k - 1];
				cache[j][k] = maxSum + triangle[j][k];
			}
		}
		maxSum = *max_element(cache[n - 1], cache[n - 1] + n);
		printf("%d\n",maxSum);
	}
}

 

[제출 결과]