[JAVA]백준 알고리즘 2775번 : 부녀회장이 될테야

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

2775번: 부녀회장이 될테야

문제

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

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

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

 

풀이

k층의 n호에 몇 명이 살고 있는지 구하는 문제이다.

 

규칙을 찾기 위해 아래 표를 그려 보았다.

 

위 표를 보면 규칙이 보일 것이다.

k층의 n호에는 (k - 1)층 n호에 사는 사람들과 k층 (n - 1)호에 사는 사람들의 수를 합한 만큼 사람이 살고 있다는 것을 알 수 있다.

이 규칙을 찾았다면 어렵지 않게 해결할 수 있다.

 

이차원 배열을 사용하여 풀 수도 있지만, 필자는 일차원 배열을 사용하여 문제를 해결하였다.

-> k층 n호에 사는 사람의 수를 구하는 데 0층 ~ (k - 1) 층까지의 사람 수는 한 번 밖에 필요하지 않기 때문에 일차원 배열의 값을 계속 덮어씌워 해결하였다.

---

🔔 자세한 코드 설명은 더보기 란에 작성하였습니다.

1. k와 n을 입력받는다.

int k = Integer.parseInt(br.readLine());
int n = Integer.parseInt(br.readLine());

 

2. 1호부터 n호까지 사람이 몇 명 사는지 저장하기 위해 크기가 n + 1인 배열을 만들었다.

int[] N = new int[n + 1];

 

3. 0층의 1호 ~ n호에는 각각 1 ~ n명이 살기 때문에, 이를 배열에 먼저 저장하였다.

for(int j = 1; j <= n; j++) {
    N[j] = j;
}

 

4. 1층부터 k층까지 점차 사람의 수를 계산해 나가기 위해 반복문을 만들었다.

4-1. 각 층의 1호에는 사람이 1명 살기 때문에, 2호부터 n호까지의 사람을 계산하였다.

* k층 n호에 사는 사람의 수 = (k - 1)층 n호에 사는 사람의 수 + k층 (n - 1)호에 사는 사람의 수이다.

* 필자는 일차원 배열을 덮어씌우는 방법으로 문제를 해결하였기 때문에, N[m] 에 N[m - 1]을 더하면 다음 층의 m호에 사는 사람의 수가 된다.

for(int j = 1; j <= k; j++) {
    for(int m = 2; m <= n; m++) {
        N[m] = N[m - 1] + N[m];
    }
}

---

코드

BufferedReader 클래스와 StringBuilder 클래스를 이용한 코드

import java.io.*;

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

        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[] N = new int[n + 1];
            for(int j = 1; j <= n; j++) {
                N[j] = j;
            }
            for(int j = 1; j <= k; j++) {
                for(int m = 2; m <= n; m++) {
                    N[m] = N[m - 1] + N[m];
                }
            }
            sb.append(N[n]).append("\n");
        }
        System.out.println(sb);
    }
}

 

틀린 부분이 있다면 정정해 주시면 감사하겠습니다.
궁금한 부분이 있거나, 다른 아이디어가 있으시면 자유롭게 댓글 남겨주세요!