백준 2775 부녀회장이 될테야 (Java)

1. 문제 링크

2775번: 부녀회장이 될테야

 

2. 문제 및 입출력예제

 

3. 문제 풀이

dp 중 쉬운 편에 속하는 문제이다.

0층에 살고 있는 사람들을 먼저 저장한다.

그것들을 바탕으로 아래층에 살고 있는 사람의 수를 더한다인 줄 알았는데 테케를 보고 점화식을 수정했다.

map[i][j] = map[i-1][j]+map[i][j-1]

한 층 아래에 살고 있는 사람과, 옆 집에 살고 있는 사람의 수를 더하면 답이 나온다.

 

4. 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;


public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int T = Integer.parseInt(br.readLine());
		for(int t=0;t<T;t++) {
			int K = Integer.parseInt(br.readLine()); //층
			int N = Integer.parseInt(br.readLine()); //호
			int[][] map = new int[K+1][N+1];

			for(int i=0;i<N+1;i++) {
				map[0][i] = i;
			}
			for(int i=1;i<K+1;i++) {
				map[i][1] = 1;
				for(int j=1;j<N+1;j++) {
					map[i][j] = map[i-1][j]+map[i][j-1];
				}
			}
			sb.append(map[K][N]).append("\n");
		}
		System.out.println(sb);
	}
}