[백준 JAVA] 단계별로 풀어보기 - 8단계 기본수학 - 2775번 부녀회장이 될테야

단계별로 풀어보기 - [8단계.기본수학1] - 2775번 부녀회장이 될테야

문제

---

문제링크

 

풀이

---

k와 n 입력값에 따라 그때그때 계산하는 것이 아니라, 층과 호에 따라 모든 아파트 거주민의 수를 이차원 배열로 만들어 놓은 다음, 테스트 케이스 값에 해당하는 것을 배열에서 꺼내서 출력해야 한다.

재귀함수로 해야 하는 줄 알았는데 그보다 이 방법이 더 간단했다.

먼저 k와 n값은 1 이상 14 이하라는 조건이 있으므로, 이차원 배열로 충분히 만들어놓을 수 있다.

apart[k][n]은 k층 n호에 사는 거주민 수이다.

모든 층의 1호는 모두 1명이고, 0층 i호에는 i명이 산다고 했으므로, 이를 먼저 세팅해준다.

그리고 나서 1층부터 14층까지 2호부터 14호까지 하나씩 채우면 된다.

k층 n호에 사는 거주민 수를 구하기 위해 규칙을 살펴보면, 다음과 같은 식으로 일반화할 수 있다.

k층 n호 거주민 수 = k층 (n-1)호 거주민 수 + (k-1)층 n호 거주민 수

 그러고 나서 테스트 케이스 개수만큼 k와 n을 입력받아서 apart[k][n]의 값을 출력해주면 끝!

 

CODE

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        int[][] apart = new int[15][15]; // [k][n]
        for (int i = 1; i < 15; i++) {
            apart[i][1] = 1; // k층 1호는 모두 1명
            apart[0][i] = i; // 0층 i호는 i명
        }
        for (int k = 1; k < 15; k++) {
            for (int n = 2; n < 15; n++) {
                apart[k][n] = apart[k][n-1] + apart[k-1][n];
            }
        }
        for (int i = 0; i < t; i++) {
            int k = sc.nextInt();
            int n = sc.nextInt();
            System.out.println(apart[k][n]);
        }
        sc.close();
    }
}