[Algospot] 삼각형 위의 최대 경로 (문제 ID : TRIANGLEPATH)

문제

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 이하의 자연수입니다.

 

출력

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

---

어렵지 않은 dp문제라 책과 다르게 풀었다. dp[i][j] = (i, j) 까지 최대 경로 값이다. (1,1) 부터 모든 경로를 조사한다. 

제일 밑 줄에서 최대 경로가 얼마인지 for문을 돌려 최대값을 구해 출력한다.

 

 

 

코드 원본 : https://github.com/chosh95/STUDY/blob/master/Algospot/TRIANGLEPATH.cpp

chosh95/STUDY

C++ 코드 

#include <iostream>
#include <memory.h>
#include <algorithm>
using namespace std;
int C, N;
int p[102][102];
int dp[102][102];

int main()
{
	cin >> C;
	while (C--) {
		cin >> N;
		for (int i = 1; i <= N; i++) 
			for (int j = 1; j <= i; j++) 
				cin >> p[i][j];
		memset(dp, 0, sizeof(dp));
		dp[1][1] = p[1][1];
		for (int i = 1; i < N; i++) {
			for (int j = 1; j <= i; j++) {
				dp[i + 1][j] = max(dp[i+1][j],(p[i+1][j] + dp[i][j]));
				dp[i + 1][j + 1] = max(dp[i+1][j+1],(p[i+1][j+1]+dp[i][j]));
			}
		}
		int res = 0;
		for (int i = 1; i <= N; i++) res = max(res, dp[N][i]);
		cout << res << "\n";
	}
}