[알고리즘-PS] 백준 2775번 부녀회장이 될테야 자바 문제풀이

문제

해당 포스팅은 백준의 2775번 부녀회장이 될테야 의 접근과 해결 방법을 설명한 글 입니다.
정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다.

이 문제를 해결하기 위해 어떤 방식으로 접근해야 하는지를 먼저 생각해보자.

문제 접근

이번 문제의 컨셉은 Dynamic Programming 이다.

해결법

0 층 부터 14층 14호 까지 존재한다고 했을 때, 다음과 같은 형태로 아파트가 존재할 것이다.

 

그리고 각 층의 인원은 아래 층의 현재 호수 까지의 인원 수의 총 합 이므로 다음과 같이 채워나갈 수 있게 되는데, 각 호수의 인원을 구하기 위해서는 n-1 층의 현재 호수 까지 존재하는 모든 인원의 합이 된다.

 

이게 바로 이 문제의 핵심이다.

 

여기서 조금 더 생각해보면 같은 층의 바로 전 호수의 인원 수와 내 바로 층의 인원 수를 합하면 현재 층과 호수의 인원을 찾을 수 있게 된다.

 

정답 코드

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

public 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[][] apartment = new int[15][15];

        apartment[0][0] = 1;

        for (int i = 0; i < apartment.length; i++) {
            apartment[0][i] = i + 1;
            apartment[i][0] = 1;
        }

        for (int i = 1; i < apartment.length; i++) {
            for (int j = 1; j < apartment[i].length; j++) {
                apartment[i][j] = apartment[i-1][j] + apartment[i][j-1];
            }
        }

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

        while (n-- > 0) {
            int floor = Integer.parseInt(br.readLine());
            int roomNumber = Integer.parseInt(br.readLine());

            bw.write(String.valueOf(apartment[floor][roomNumber-1]));
            bw.write("\n");
        }
        bw.flush();
        bw.close();
    }
}

---

문제 회고

회고

정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다.