https://www.acmicpc.net/problem/2775
2775번: 부녀회장이 될테야
첫 번째 줄에 Test case의 수 T가 주어진다. 그리고 각각의 케이스마다 입력으로 첫 번째 줄에 정수 k, 두 번째 줄에 정수 n이 주어진다
www.acmicpc.net
코드설명
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);
}
}