[Java] 백준(브론즈-1) 2275번 - 부녀회장이 될테야

제한 사항

• 1 ≤ k, n ≤ 14

입출력 예시

Input

2
1
3
2
3

Output

6
10

문제 풀이

---

이 문제는 주어진 k,n을 가지고 k층에 n호에 몇명이 거주하는지 구해야 한다.
0층에는 i호에 i명이 거주함을 보고 0층부터 k층의 n호까지 구해나가야 함을 알 수 있다.

k층의 n호는 전층 즉, k-1층의 1호~n호까지의 합이 된다.

0층 - 1호:1명, 2호:2명, 3호:3명 ...
1층 - 1호:1명, 2호:3명, 3호:6명 ...
2층 - 1호:1명, 2호:4명, 3호:10명 ...
3층 - 1호:1명, 2호:5명, 3호:15명 ...
2층 - 1호:1명, 2호:6명, 3호:21명 ...
...

합배열 활용하기

k-1층의 1부터 n까지의 합이 k층의 n호 값이 되기 때문에 합배열을 활용하여 층마다 합배열을 만들면 된다.
0층은 i호에 i명이 사니까 1층의 합배열을 만들어놓고 2층~14층까지의 k가 주어지면 k만큼 돌면서 합배열을 만들어 주자.
그렇게 만든 합배열의 n번째 원소가 k층의 n호의 거주자 수가 된다.

합배열을 활용하여 코드를 작성해보자.

int T = Integer.parseInt(br.readLine());
for(int i=0; i<T; i++) {
    int k = Integer.parseInt(br.readLine());
    int n = Integer.parseInt(br.readLine());
}

먼저 테스트케이스 개수 T를 입력받고 T만큼 순회하며 k와 n을 개행단위로 입력받는다.

int[] firstFloor = new int[n+1];
for(int j=1; j<=n; j++) {
    firstFloor[j] += firstFloor[j-1]+j;
}

그리고 0층의 n호만큼 돌며 1층의 n호까지의 거주자 수를 합배열로 저장한다.

int floor = 1;
while(floor < k) {
    for(int j=2; j<=n; j++) {
        firstFloor[j] += firstFloor[j-1];
    }
    floor++;
}
bw.write(firstFloor[n]+"\n");

1층의 거주자 수를 알았으니, k층에 도달할 때까지 전층의 n호까지 거주자 합을 배열에 저장해나간다.
floor가 k-1 값이 된다면 while문을 탈출하고 firstFloor[n] 의 값을 통해 k층 n호 거주자 수를 구할 수 있다.

작성코드

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

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        int T = Integer.parseInt(br.readLine());

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

            int[] firstFloor = new int[n+1];
            for(int j=1; j<=n; j++) {
                firstFloor[j] += firstFloor[j-1]+j;
            }
            
            int floor = 1;
            while(floor < k) {
                for(int j=2; j<=n; j++) {
                    firstFloor[j] += firstFloor[j-1];
                }
                floor++;
            }
            bw.write(firstFloor[n]+"\n");
        }
        
        bw.flush();
        bw.close();
        br.close();
    }
 }

회고

• 문제를 보고 각 k층에 거주자 수를 구하기 위해서 k-1층의 거주자 수들을 알아야 하기 때문에 가장 낮은 층부터 순차적으로 구해 나가야 함을 빠르게 알 수 있었다.