[백준] 2775번 : 부녀회장이 될테야 – JAVA [자바]

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

2775번: 부녀회장이 될테야

 

---

• 문제

 

 

---

• 문제 풀이

백준 2775번 부녀회장이 될테야는 브론즈 1 난이도의 수학 및 구현 문제이다. 이 문제에서는 테스트 케이스의 개수 T가 주어지고 각 테스트 케이스마다 정수 k와 n도 같이 주어진다. 그리고 k층 n호에 몇 명이 사는지를 출력하면 되는 문제이다.

 

이 문제에서는 추가 조건도 있다. 바로 “a층의 b호에 살려면 자신의 아래(a-1)층의 1호부터 b호까지 사람들의 수의 합만큼 사람들을 데려와 살아야 한다”는 조건이다. 추가로 0층 i호에는 무조건 i명이 산다고 문제에 명시되어 있다.

 

이 문제는 2차원 배열을 이용해서 풀 수가 있다. 우선 2차원 배열 arr을 선언하고 arr [k][n]은 k층 n호를 뜻한다고 가정하겠다.

 

이제 문제에서 주어진 예시들을 보면서 문제를 풀어보겠다.

 

EX 1) k = 1, n = 3

 

이 예시에서는 1층 3호에 몇 명이 사는지를 출력해야 한다. 현재 상황을 표시하면 밑에 있는 표와 같다.

 

1층 3호에 몇 명이 사는지를 구하려면 아래층, 즉 0층 3호까지 사는 사람의 합을 구해야 한다. 즉 1 + 2 + 3 = 6명이다.

 

즉, arr [n][k]를 구하려면 arr [n - 1][1]부터 arr [n - 1][k]까지 구해야 한다. 

 

하지만, 조금 더 쉽게 구할 수 있는 방법이 있다. 바로 arr [n][k - 1]이 바로 arr [n - 1][1]부터 arr [n - 1][k - 1]까지의 합이라는 것이다. 그림으로 표시하면 다음과 같다.

 

 

빨간색으로 표시되어 있는 부분은 서로 같다. 따라서 arr [n][k]를 구하려면 arr [n][k - 1] + arr [n - 1][k]를 하면 된다.

 

arr [n][k] = arr [n][k - 1] + arr [n - 1][k]

 

자세한 코드는 밑에 있다.

 

---

• 코드

 

import java.io.*;
import java.util.*;
public 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[][] arr = new int[15][15];
        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= 14; i++) {
            arr[0][i] = i;  //0층 i호에는 무조건 i명이 산다
        }

        
        for (int i = 1; i <= 14; i++) {
            for (int j = 1; j <= 14; j++) {
                arr[i][j] = arr[i][j-1] + arr[i-1][j];
            }
        }
        for (int i = 0; i < t; i++) {
            int k = Integer.parseInt(br.readLine());
            int n = Integer.parseInt(br.readLine());
            sb.append(arr[k][n] + "\n");  //k층 n호에 있는 사람 수 출력
        } 
        System.out.print(sb);
    }
}