[JAVA] 백준 2775 DP

 

 

 

 

2775번: 부녀회장이 될테야

문제

평소 반상회에 참석하는 것을 좋아하는 주희는 이번 기회에 부녀회장이 되고 싶어 각 층의 사람들을 불러 모아 반상회를 주최하려고 한다.

이 아파트에 거주를 하려면 조건이 있는데, “a층의 b호에 살려면 자신의 아래(a-1)층의 1호부터 b호까지 사람들의 수의 합만큼 사람들을 데려와 살아야 한다” 는 계약 조항을 꼭 지키고 들어와야 한다.

아파트에 비어있는 집은 없고 모든 거주민들이 이 계약 조건을 지키고 왔다고 가정했을 때, 주어지는 양의 정수 k와 n에 대해 k층에 n호에는 몇 명이 살고 있는지 출력하라. 단, 아파트에는 0층부터 있고 각층에는 1호부터 있으며, 0층의 i호에는 i명이 산다.

풀이

0층의 i호에는 i명이 살고있고, a층 b호에 살려면 a-1층 1 ~ b호까지의 사람들의 수를 합만큼 사람들을 데려와서 살아야 한다.

이를 토대로 점화식을 만들 수 있었다.

📌 배열 초기화

        for(int i=0; i<D.length; i++){
            D[0][i] = i;
        }

문제에서 0층의 i호에는 i명이 살고 있다고 했기 때문에 이를 토대로 초기화해주었다.

📌 점화식으로 배열 채우기

        for(int i=1; i<D.length; i++){
            for(int j=1; j<D.length; j++){
                D[i][j] = D[i][j-1] + D[i-1][j];
            }
        }

1. D[1][1], 1층의 1호에 사는 사람들은 0층의 1호에 사는 사람만큼 있으면 된다.
2. D[1][2], 1층의 2호에 사는 사람들은 0층의 1호 + 0층의 2호에 사는 사람만큼 있으면 된다.
3. D[1][3], 1층의 3호에 사는 사람들은 0층의 1호 + 0층의 2호 + 0층의 3호에 사는 사람만큼 있으면 된다.

무언가 보인다. 바로 같은 층의 이전 호실에 있는 사람의 수 + 아래 층의 호실에 있는 사람의 수가 바로 현재 a층 b호의 사람이 된다.

따라서 점화식은 다음과 같이 만들어진다.

D[i][j] = D[i][j-1] + D[i-1][j], i층 j호의 사는 사람은 i층 j-1호 + i-1층 j호에 사는 사람들의 합과 같다.

📌 전체 코드

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

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        int[][] D = new int[15][15];

        for(int i=0; i<D.length; i++){
            D[0][i] = i;
        }

        for(int i=1; i<D.length; i++){
            for(int j=1; j<D.length; j++){
                D[i][j] = D[i][j-1] + D[i-1][j];
            }
        }

        StringBuilder sb = new StringBuilder();
        for(int i=0; i<T; i++){
            int a = Integer.parseInt(br.readLine());
            int b = Integer.parseInt(br.readLine());

            sb.append(D[a][b]).append("\n");
        }
        System.out.println(sb);

    }
}

결과