[백준] 2775번_부녀회장이 될테야(Java)

문제 풀이

백준의 2775번 문제입니다. 문제 출처

(1) 문제 파악

아파트 각 호수의 인원이 어떠한 규칙예 따라 정해져있고 특정 호수의 거주민 수를 출력하는 문제입니다.

입력은 1<=k,n<=14 로 작게 주어집니다.

(2) 문제 풀이 방법 생각하기

a층의 b호에는 a-1층의 1호부터 b호까지 인원 수 +1의 사람이 살게 될 것입니다.

\[arr[a][b] = (\sum_{i=1}^b arr[a-1][i])+ 1\]

여기서 a-1층의 1호부터 b-1호까지 인원 수 +1은 arr[a][b-1] 이므로 아래와 같은 식이 만들어집니다.

\[arr[a][b] = arr[a-1][b] + arr[a][b-1]\]

(3) 시간 복잡도 확인

시간 제한은 0.5초 입니다. 즉, 대략 5천만번 연산 안에 문제를 해결해야 합니다.

15 * 15 = 225 이므로 이중 for 문을 사용해도 충분히 해결할 수 있습니다.

(4) 구현

입력의 크기가 작으므로 테스트 케이스마다 배열을 생성하기 보다는 미리 하나의 배열을 생성하여 계산을 한 뒤에 원하는 특정 호수의 인원을 출력하는 방식으로 작성하였습니다.

import java.io.*;

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

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

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

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

            System.out.println(apartment[k][n]);
        }

        br.close();
    }
}

참고로 apartment 배열을 미리 생성하지 않고 케이스마다 입력 크기대로 생성하는 경우에는 메모리를 더 차지할 것이라고 예상했는데 입력의 크기가 작아서 그런지 메모리를 덜 차지하네요..!

(1) 배열 미리 생성한 경우

(2) 케이스마다 배열을 생성한 경우