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

  목 차

• 문제
• 접근 방식
• 풀이

 

---

  문제

 

 

 

 

  접근 방식

 

먼저 기본값인 [0] 층의 1~14호 까지를 입력한다.

 

그리고 [1] 층의 1~14호 까지 입력한다.

 

그리고 더욱 정확한 비교를 위해서 [2]층의 일부분 호수를 입력한다.

 

 

처음 숫자는 모두 1로 동일하다. 생각해 보면 [k][n - 1]은 이미 구했던 [k - 1][1] 부터 [k - 1][n - 1] 까지의 합이다.

그럼 여기에 아래층의 같은 호수만 더하면 현재 호수가 된다.

 

말이 좀 복잡한데 그림으로 알아보자.

 

 

먼저 표를 확인 훑고 아래 이미지를 확인해 보자.

k 층의 n 호

dp[k][n]

[0][n] = 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14

[1][n] = 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 66, 78, 91, 105 

[2][n] = 1, 4, 10, 20,35, 56, 84, … … ...

 

 

 

 

점화식: dp[k][n] = dp[k - 1][n] + dp[k][n - 1];

 

 

 

 

  풀이

 

package src.dp;

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

public class I_want_president {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int n = Integer.parseInt(br.readLine());

        int[][] input = new int[n][2];

        for(int i = 0; i < n; i++){
            input[i][0] = Integer.parseInt(br.readLine());
            input[i][1] = Integer.parseInt(br.readLine());
        }

        int[][] dp = new int[15][15];

        // dp 기본값
        for(int i = 1; i <= 14; i++){
            dp[0][i] = i;
        }

        for(int i = 1; i <= 14; i++){

            for(int j = 1; j <= 14; j++){
                if(j == 1){
                    dp[i][j] = 1;
                } else {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }
            }

        }

        for(int el[] : input){
            int k = el[0];
            int i = el[1];

            int data = dp[k][i];

            sb.append(data).append('\n');

        }

        System.out.println(sb);


    }
}