[백준/1010] 다리놓기 - 동적계획법/메모이제이션/top-down

dp 너무너무 헷갈린다. 실버 5 푸는데 머리 안돌아가서 하루종일 붙잡고있었네...... 욕심 안부리고 오늘은 dp 이해하기로..^_^..

 

package silver5;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.StringTokenizer;

public class Main_1010_다리놓기_조합dp {
	static int M,N, answer;
	static int [][] dp;
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		for(int t=0; t<T; t++) {
			StringTokenizer st = new StringTokenizer(br.readLine()," ");
			N=Integer.parseInt(st.nextToken());
			M=Integer.parseInt(st.nextToken());
			dp=new int[M+1][N+1];
			answer=0;
			for(int m=0; m<M; m++) {
				dp[m][0]=1;
				dp[m][1]=m;
			}
			answer = combination(M,N);
			// mCn = m-1Cn-1 + m-1Cn
			// 4C2 = 3C1					+					3C2
			//		 2C1	+	2C0			+	2C2 		+	2C1
			//		 1C1+1C0+	1C0+(1C-1=0)+	(1C2=0)+1C1 + 	1C1+1C0
			System.out.println(answer);
		}
	}

	// cnt 쓰는거랑 n,r 쓰는거 차이를 알아야됨
	// 둘 다 써야하는건가? 진짜 헷갈리네
	private static int combination(int n, int r) {
		if(n<0||r<0||n<r) {
//			System.out.println("범위벗어남");
				return 0;
		}else if(dp[n][r]>0) {
//			System.out.println(dp[n][r]);
			return dp[n][r];
		}else {
			dp[n-1][r]=combination(n-1,r);
			dp[n-1][r-1]=combination(n-1,r-1);
//			System.out.println("dp[n-1][r] + dp[n-1][r-1] = " + dp[n-1][r] + " / " + dp[n-1][r-1]);
			return dp[n-1][r]+dp[n-1][r-1];
		}
		
			
	}
}

 

순열조합 코드 익히니까 아주 조금 익숙해지긴했는데 한번더 정리하면

 

1. 규칙찾기 mCn = m-1Cn-1 + m-1Cn

2. 같은 계산이 여러번 반복되면 배열 만들어서 때려넣기 static int [][] dp; 

3. combination 함수 만들고,

3-1. 탈출할 부분

3-1-1 if(조합에서 있을수 없는 조건) return 0

3-1-2 if(메모이제이션 되어있는 값이라면) return 그 값

3-2. 재귀 들어갈 부분

 

끝.... 재귀를 쓸꺼면 탈출하는 부분 신경써야된다그랬음... 

 

+ 좀 헷갈리는부분

지금 코드에서는 초기값.....을 미리 지정해두고 위에서부터 쭈욱 내려갔다가 그 값 발견하면 계산하면서 다시 올라오는건데... 이렇게하는게 맞는건가.... 그냥 처음부터 아래서부터 시작하는건가? 헷갈린다 또 ^_^.... 다음 문제 풀어보면서 다시 정리해봐야지...

 

참고해볼자료, 읽고 다음문제 풀자

coding-all.tistory.com/2

동적계획법(Dynamic Programing, DP)