[백준] 2775번 - 부녀회장이 될테야 (Java)

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

2775번: 부녀회장이 될테야

 

<문제 분석>

* 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]]);
		}
	}
}

 

<제출 결과>