문제
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
Concept
완전 탐색시 시간초과 날 것이 자명하므로 DP를 수행하기로 하자
Code
#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
int n;
int arr[101][101];
int cache[101][101];
int triangle2 (int row, int col){
if (row==n-1) return arr[row][col];
if (cache[row][col] != -1) return cache[row][col];
return cache[row][col] = max(triangle2(row+1, col), triangle2(row+1, col+1)) + arr[row][col];
}
int main(){
int c;
cin>>c;
for (int i=0; i<c; i++){
cin>>n;
for (int j=0; j<n; j++){
for (int k=0; k<=j; k++){
cin>>arr[j][k];
}
}
memset(cache, -1, sizeof(cache));
cout<<triangle(0,0)<<endl;
}
}
Comment
int triangle(int row, int col){ //cache는 해당 값 밑으로의 비용의 합을 저장함
//줄 넘어가면 종료
if (row==n) return cache[row][col] = 0;
//이미 계산된 cache가 있으면 그 값 리턴
if (cache[row][col] != -1) return cache[row][col];
// 아래로 갈 경우 재귀적으로 계산
int down = arr[row][col] + triangle(row+1, col);
// 아래 오른쪽으로 갈 경우 재귀적 계산
int right = arr[row][col] + triangle(row+1, col+1);
return ( down > right)? cache[row][col] = down : right;
}와 본질적으로 동일해보이는데, 이 함수는 시간초과가 발생한다. 아무리 봐도 원인을 모르겠다.
deprecated