[백준] 2775 부녀회장이 될테야 - DP(Dynamic Programming) JAVA

https://www.acmicpc.net/problem/2775

2775번: 부녀회장이 될테야

코드설명

DP(Dynamic Programming) 을 활용합니다.

 

문제에서 바텀업 방식으로 접근했습니다.

층 / 호	1	2	3
0	1	2	3
1	1	3	6
2	1	4	10
3	1	5	15

 

위와 같이 표를 나타낼 수 있는데, 이를 일반화시키면

dp[i][j] = dp[i][j-1] + dp[i-1][j] 로 표현할 수 있습니다. 단 j >= 2 부터입니다.

 

조금 더 쉽게 표현해보면

dp[현재층][현재 호수] = dp[현재층][현재 호수 - 1] + dp[현재층 -1][현재호수] 로 표현할 수 있습니다.

코드

package algorhythm;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map.Entry;
import java.util.StringTokenizer;

public class Main {
	public static int N, M, T;
	public static int answer = 0;
	public static int[][] dp = new int[15][15];
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		T = Integer.parseInt(st.nextToken());
		
		//0층 0 호부터 ~ 0 층 14호까지 col 명으로 초기화합니다.
		for(int col=0;col<15;col++) {
			dp[0][col] = col + 1;
		}
		
		//일반화시킬 것 입니다.
		for(int i=1; i<15;i++) {
			dp[i][0] = 1;
			for(int j=1; j<15;j++) {
				dp[i][j] = dp[i][j-1] + dp[i-1][j];
			}
		}
		
		for(int t = 0; t < T; t++) {
			st = new StringTokenizer(br.readLine());
			int k = Integer.parseInt(st.nextToken());
			st = new StringTokenizer(br.readLine());
			int n = Integer.parseInt(st.nextToken());
			System.out.println(dp[k][n-1]);
		}
		
//		System.out.println(answer);
	}
}