TRIPATHCNT

■ 문제

아래와 같이 삼각형이 주어질 때 맨 위의 숫자에서 시작해, 한 번에 한 칸씩 아래로 내려가 맨 아래 줄로 내려가는 경로를 만들려고 한다. 경로의 합이 최대인 최대 경로의 갯수를 세는 프로그램을 작성하세요.

9
5 7
1 3 2
3 5 5 6

[조건]

1) 경로는 아래 줄로 내려갈 때마다 바로 아래 숫자, 혹은 오른쪽 아래 숫자로 내려갈 수 있다. 

2) 삼각형을 이루는 수는 자연수

■ 풀이

기존에 풀었던 TRIANGLEPATH 문제와 접근법은 동일하다. 다만, 최대 경로 크기 계산 목적인 cache[i][j] 값과 더불어 최대 경로 갯수에 대한 pathCache[i][j]를 추가적으로 계산하면서 [0, 0] 까지 올라와야 한다.

풀이 핵심은 경로의 최대값 cache[i][j]을 위한 아래 경로 크기(이하 down), 오른쪽 아래 경로(이하 rightDown) 크기값에 따라 2가지 경우를 나누어 처리하는 것이다. 즉, 현재 위치인 cache[i][j]에서 아래 경로 크기(cache[i+1][j])와 오른쪽 아래 경로 크기(cache[i+1][j+1])크기를 비교 하는 것이다. 경로의 갯수 결정은 경로의 크기에 종속됨이 핵심이다. 경로 갯수 저장을 위한 캐시 저장소 pathCache[i][j]를 선언하여 관리한다.

1. down == rightDown 인 경우

이 조건이 중요하다. 현 위치인 i, j에서 2가지 경로 중 최대 값을 선택해야 하지만, 두 경로 크기가 같기 때문에 두 경로 모두 i, j 경로에 포함되어야 한다. 만약 down의 경로가 2개, rightDown 경로가 3개라면, 현재 경로는 두 경로를 합친 5개 경로가 된다.
    → pathCache[i][j] = pathCache[i+1][j] + parhCache[i+1][j+1]

나머지 조건은 경로 크기에 따라 경로 갯수가 결정된다.

2. down > rightDown 인 경우
    두 경로 중 경로 크기가 큰 값을 선택하면 된다. 
    → pathCache[i][j] = pathCache[i+1][j]

3. down <  rightDown 인 경우
    → pathCache[i][j] = pathCache[i+1][j+1]

그림으로 표현하면 아래와 같다.

이 알고리즘은 최대 n개의 부문 문제가 있고, 부문 문제를 해결하는 데 최대 두 개의 부문 문제를 포함한다. 따라서, 시간복잡도는 O(n)이다.