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

문제

- 이 아파트에는 "a층의 b호에 살려면 자신의 아래 (a-1)층의 1호부터 b호까지 사람들의 수의 합만큼 사람들을 데려와 살야아 한다."는 계약 조건이 있음

- 아파트에 비어있는 집은 없고 모든 거주민들이 이 계약 조건을 지킴

- 주어지는 양의 정수 k와 n에 대해 k층에 n호에는 몇 명이 살고 있는지 출력

- 아파트는 0층부터 있고 각 층에는 1호부터 있으며, 0층의 i호에는 i명이 살고 있음

 

해결방법

문제에서 설명하는 것처럼 "a층의 b호에 살려면 자신의 아래 (a-1)층의 1호부터 b호까지 사람들의 수의 합만큼 사람들을 데려와 살야아 한다."를 만족시키려면 0층과 1호에는 기본적으로 값(0층엔 호수대로, 1호엔 무조건 1명)을 세팅해준 뒤 나머지에 값을 채워야 한다.

문제에 제시된 대로 식을 작성하면 k층 n호 = (k-1)층 1호 ~ (k-1)층 n호의 합이다. 그렇기 때문에 k층 (n-1)호에 저장된 값고 (k-1)층 n호에 저장된 값을 더하면 해당 값을 찾아낼 수 있다.

즉, k층 n호 = k층 (n-1)호 + (k-1)층 n호와 같은 식으로 구할 수 있다.

빨간색으로 표시된 칸은 백준 테스트케이스에서 구한 값을 표시해 둔 것이다.

 

코드

import java.io.*;
import java.util.*;

class Main{
    public static void main(String[] args) throws Exception {
       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       int T = Integer.parseInt(br.readLine());
       int[][] apt = new int[15][15];

       for(int i = 0; i<15; i++){
           apt[0][i] = i;	// 0층 채우기
           apt[i][1] = 1;	// 1호 채우기
       }

       for(int tc = 1; tc<=T; tc++){
           int k = Integer.parseInt(br.readLine());
           int n = Integer.parseInt(br.readLine());

           for(int i = 1; i<=k; i++){
               for(int j = 0; j<=n; j++){
                   if(apt[i][j] == 0){
                       // 입력 받은 층, 호까지 숫자들을 채워 줌
                       // 현재 층 이전 호수 + 이전 층 현재 호수
                       apt[i][j] = apt[i][j-1] + apt[i-1][j];
                   }
               }
           }
           System.out.println(apt[k][n]);	// 필요한 정보 출력
       }


       br.close();
    }
}