알고리즘 PS/백준 알고리즘
[백준] 2775번 - 부녀회장이 될테야 (Java)
백호루이
2022. 9. 28. 16:14
반응형
https://www.acmicpc.net/problem/2775
2775번: 부녀회장이 될테야
첫 번째 줄에 Test case의 수 T가 주어진다. 그리고 각각의 케이스마다 입력으로 첫 번째 줄에 정수 k, 두 번째 줄에 정수 n이 주어진다
www.acmicpc.net
<문제 분석>
* DP(Dynamic Programming) 문제 푸는 공식 3단계
1) DP 테이블 정의
- a층의 b호에 살려면 자신의 아래(a-1)층의 1호부터 b호까지 사람들의 수의 합
2) 점화식 찾기
- DP[k][n] = DP[k-1][1] + ... + DP[k-1][n]
3) 초기값 정하기
- DP[0][1] ~ DP[0][14]까지 호실 번호와 동일한 사람수를 가진다.
DP 테이블을 2중 배열을 사용해서 세로축은 층수, 가로축은 호실 번호를 적용했다.
이전 DP문제와 동일하게 미리 DP테이블 값을 다 구해놓고 입력값은 나중에 출력할 때만 사용했다.
<코드 구현>
import java.util.Scanner;
import java.lang.Math;
//[백준] 2775번 - 부녀회장이 될테야 (Java)
public class Main {
static int T;//입력 데이터의 개수
static final int MAX = 14;
static int Data[][];
static int DP[][] = new int[MAX+1][MAX+1];
public void InputData()
{
Scanner sc = new Scanner(System.in);
T = sc.nextInt();
Data = new int[T][2];
for (int i = 0; i < T; i++)
{
Data[i][0] = sc.nextInt(); // 층수
Data[i][1] = sc.nextInt(); // 호실
}
sc.close();
}
public void Solve() {
// 1.DP 테이블 초기화 및 값 종류 정하기
for (int i=0; i<=MAX; i++) {
for (int j=1; j<=MAX; j++) {
DP[i][j] = -1;
}
}
// 2. 초기값 설정
for (int i=1; i<=MAX; i++) {
DP[0][i] = i;
}
// 3. 정화식 구현
for (int i=1; i<=MAX; i++) {
int tmp_dp = 0;
for (int j=1; j<=MAX; j++) {
int tmp = 0;
for (int k=1; k<=j; k++) {
tmp += DP[i-1][k];
}
DP[i][j] = tmp;
}
}
}
public static void main(String[] args)
{
Main m = new Main();
m.InputData();///입력
//코드를 작성하세요
m.Solve();
// for (int i = 0; i <=MAX; i++) {
// for (int j=1; j<=MAX; j++) {
// System.out.print(DP[i][j]+" ");
// }
// System.out.println();
// }
//출력
for (int i = 0; i < T; i++)
{
System.out.println(DP[Data[i][0]][Data[i][1]]);
}
}
}
<제출 결과>
반응형