[종만북][알고스팟] 삼각형 위의 최대 경로 개수 세기 (TRIPATHCNT) - 동적계획법(Dynamic Programming) JAVA

https://www.algospot.com/judge/problem/read/TRIPATHCNT

algospot.com :: TRIPATHCNT

코드설명

동적계획법을 활용합니다.

 

이 문제는 이전에 삼각형 위의 최대 경로의 합을 이용하여 해결할 수 있습니다.

예로 들어,

아래의 삼각형이 주어졌다고 가정합니다.

9
5 7
1 3 2
3 5 5 6

삼각형의 최대경로의 합을 구하면, 아래와 같습니다.

아래의 최대경로의 합을 구하는 방법은,

:path(r, c) : (r, c)에서 맨 아래줄까지 내려가는 부분 경로의 최대합을 반환한다." 라는 함수를 정의하여 구할 수 있습니다.

24
13 15
6 8 8
3 5 5 6

이제 우리는 24가 나오는 경로의 개수가 몇개인지 구하면 됩니다.

이는 

"count(r, c) : (r, c)에서 맨 아래줄까지 내려가는 최대 경로의 수를 반환한다." 라는 함수를 정의하여 구할 수 있습니다.

이는 다음과 같은 점화식을 정의할 수 있습니다.

count(r, c) = count(y + 1, x) ( path(y+1, x) > path(y+1, x + 1) )

                    count(y + 1, x + 1) ( path(y + 1, x) < path(y + 1, x + 1) )

                    count(y + 1, x) + count(y + 1, x + 1) ( path(y + 1, x)  == path(y + 1, x + 1) )

위의 점화식을 사용하여 구할 수 있습니다.

 

코드

메모이제이션을 적용한 코드입니다.

package Main;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
	public static int C, N, M, S;
	public static int answer = 0;
	public static String Num;
	public static int[][] cache, cache2;
	public static int[][] map;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		C = Integer.parseInt(st.nextToken());
		while(C-- >0) {
			st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			map = new int[N][N];
			cache = new int[N][N];
			cache2 = new int[N][N];
			
			for(int i=0;i<N;i++) {
				Arrays.fill(cache[i], -1);
				Arrays.fill(cache2[i], -1);
				st = new StringTokenizer(br.readLine());
				for(int j=0;j<=i;j++) {
					map[i][j] = Integer.parseInt(st.nextToken());
				}
			}
			
//			for(int i=0;i<N;i++) {
//				for(int j=0;j<=i;j++) {
//					System.out.print(map[i][j]);
//				}
//				System.out.println();
//			}
//			System.out.println();
			
			System.out.println(count(0, 0));
		}
		
	}
	
	
	//(r, c)에서 시작해서 맨 아랫줄까지 내려가는 경로 중 최대 경로의 개수를 반환한다.
	public static int count(int r, int c) {
		//기저사례 : 맨 아래줄에 도달한 경우
		if(r == N - 1) return 1;
		if(cache[r][c] != -1) return cache[r][c];
		
		int result = 0;
		if(path2(r + 1, c) >= path2(r + 1, c + 1)) result += count(r + 1, c);
		if(path2(r + 1, c)<= path2(r + 1, c + 1)) result += count(r + 1, c + 1);
		return cache[r][c] = result;
	}
	
	public static int path2(int r, int c) {
		if(r == N - 1) return map[r][c];
		if(cache2[r][c] != -1) return cache2[r][c];
		
		int result = 0;
		result = Math.max(path2(r + 1, c), path2(r + 1, c + 1)) + map[r][c];
		return cache2[r][c] = result;
	}
}

 

메모이제이션을 적용한 두번쨰 코드입니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
	public static int C, N, M, S;
	public static int answer = 0;
	public static int[][] map, cache, countCache;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		C = Integer.parseInt(st.nextToken());
		while(C-- >0) {
			st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			map = new int[N][N];
			cache = new int[N][N];
			countCache = new int[N][N];
			for(int i=0;i<N;i++) {
				Arrays.fill(cache[i], -1);
				Arrays.fill(countCache[i], -1);
			}
			for(int i=0;i<N;i++) {
				st = new StringTokenizer(br.readLine());
				for(int j=0; j<=i;j++) {
					map[i][j] = Integer.parseInt(st.nextToken());
				}
			}
			
			System.out.println(count(0, 0));
		}
		
	}
	
	
	public static int count(int r, int c) {
		if(r == N-1) {
			return 1;
		}
		if(countCache[r][c] != -1) return countCache[r][c];
		
		int ret = 0;
		if( trianglePath(r + 1, c) >= trianglePath(r + 1, c + 1)) ret += count(r + 1, c);
		if( trianglePath(r + 1, c) <= trianglePath(r + 1, c + 1)) ret += count(r + 1, c + 1);
		return countCache[r][c] = ret;
	}
	
	public static int trianglePath(int r, int c) {
		if(r == N-1) {
			return map[r][c];
		}
		if(cache[r][c] != -1) return cache[r][c];
		
		int ret = 0;
		ret = Math.max( trianglePath(r + 1, c), trianglePath(r + 1, c + 1) ) + map[r][c];
		return cache[r][c] = ret; 
	}
	
	
}