[알고스팟] TRIPATHCNT - 삼각형 위의 최대 경로 수 세기 (C++)
문제
algospot.com/judge/problem/read/TRIPATHCNT
algospot.com :: TRIPATHCNT
삼각형 위의 최대 경로 수 세기 문제 정보 문제 9 5 7 1 3 2 3 5 5 6 위 형태와 같이 삼각형 모양으로 배치된 자연수들이 있습니다. 맨 위의 숫자에서 시작해, 한 번에 한 칸씩 아래로 내려가 맨 아래
algospot.com
풀이
종만북 난이도: 중
난이도는 중인 DP문제이지만 이전 단계를 풀었다면 쉬운 문제이다.
일단 이전 단계 문제인 삼각형 위의 최대 경로를 풀고오자.
최대 경로의 값을 구하는 문제는 아래와 같은 재귀함수로 해결이 가능하다.
|
1
2
3
4
5
6
7
8
9
10
11
|
int TriMaxSum(int r,int c){
int& ret = cache_max[r][c];
if(r == tri_size -1)
return ret= triangle[r][c];
if(ret != -1)
return ret;
ret = triangle[r][c]+ max(TriMaxSum(r+1 , c), TriMaxSum(r+1, c+1));
return ret;
}
|
cs |
해당 함수를 통해 우리는 cache_max[r][c] 값이 cache_max[r+1][c]와 cache_max[r+1][c+1] 값 중에 더 큰 값과 자신의 위치인 triangle[r][c] 값을 더한 값을 저장하도록 만들었다.
cache_max[r][c] = triangle[r][c]+ max(TriMaxSum(r+1 , c), TriMaxSum(r+1, c+1))
우리는 이 cache_max를 이용하여 최대 경로의 개수를 구할 것이다.
int TriPathCnt(int r,int c) 는 r,c 위치에서 이동 가능한 최대 경로의 수를 반환한다.
cache_path[r][c]에 해당 위치에서 이동 가능한 최대 경로의 수를 저장한다고 하자.
(r,c)위치에서 분기가 가능한 최대 경로의 가지 수는 3가지이다.
1. cache_max[r+1][c] > cache_max[r+1][c+1]
(r+1,c)만이, 즉 한 가지 경로만 최대 경로가 되므로 cache_path[r+1][c]의 값과 같다.
cache_path[r][c] = TriPathCnt(r+1, c)
2. cache_max[r+1][c] < cache_max[r+1][c+1]
(r+1,c+1)만이 최대 경로가 되므로 cache_path[r+1][c+1]의 값과 같다.
cache_path[r][c] = TriPathCnt(r+1, c+1)
2. cache_max[r+1][c] == cache_max[r+1][c+1]
(r+1,c)와 (r+1,c+1)두 경로가 모두 최대 경로가 되므로 cache_path[r+1][c] + cache_path[r+1][c+1]의 값과 같다.
cache_path[r][c] = TriPathCnt(r+1, c) + TriPathCnt(r+1, c+1)