[알고스팟] TRIPATHCNT - 삼각형 위의 최대 경로 수 세기 (C++)

문제

algospot.com/judge/problem/read/TRIPATHCNT

algospot.com :: TRIPATHCNT

 

풀이

종만북 난이도: 중

 

난이도는 중인 DP문제이지만 이전 단계를 풀었다면 쉬운 문제이다.

일단 이전 단계 문제인 삼각형 위의 최대 경로를 풀고오자.

 

최대 경로의 값을 구하는 문제는 아래와 같은 재귀함수로 해결이 가능하다.

 

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;
}

 

해당 함수를 통해 우리는 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)

 

 

코드