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

문제

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

2775번: 부녀회장이 될테야

 

코드

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        StringBuffer sb = new StringBuffer();
        int T = sc.nextInt();
        int[] floor = new int[15];     // 한 층의 거주자 수

        for (int t = 0; t < T; t++) {
            // 0층 각 호 거주자 수 초기화
            for (int i = 0; i < floor.length; i++) {
                floor[i] = i;
            }
            
            int k = sc.nextInt();
            int n = sc.nextInt();

            // 1층 ~ k층
            for (int i = 1; i <= k; i++) {
                // 1호 ~ n호
                for (int j = 1; j <= n; j++) {
                    floor[j] += floor[j - 1];
                }
            }
            sb.append(floor[n] + "\n");
        }
        System.out.print(sb);
    }
}

 

풀이

층은 0부터 시작하며, 호는 1부터 시작함에 주의하자. 입력 조건이 [1 ≤ k, n ≤ 14] 로 되어 있지만, 이는 입력으로 받을 층 수(k)가 1보다 크다는 것이지 이 아파트가 1층부터 시작한다는 뜻이 아니다.

즉, 문제에서 주어진 아파트는 0층 부터 시작하며, 각 층은 1호 부터 시작해 최대 14호까지 이어지는 구조이다. (층수 k는 최대값 제한이 없음)

호는 최대 14호까지, 층은 제한이 없음

 

아파트의 구조를 알았으니, 이제 'k층 n호 거주자 수'를 어떤 값으로 부터 산출할 수 있는지 생각해보자. k층 n호 거주자 수는 k-1층의 1호~n호 거주자 수의 합이라 했는데, 두번째 테스트케이스인 '2층 3호의 거주자 수'를 예시로 생각해보자

문제에서 주어진 말 그대로 단순히 생각하면, 2층 3호 거주자 수는 1층 1호부터 3호까지의 거주자 수를 합한 값(1+3+6=10)이 된다. 그러나 이렇게 아래 층의 3호까지의 값을 하나씩 더해서 결과값을 구하면 층, 호가 커질수록 효율이 떨어진다.(ex: 10층 14호의 거주자 수를 알려면 9층 1호~14호 거주자 수를 전부 더해야 함) 규칙을 찾아내면 앞서 계산된 값을 이용해서 적은 연산만으로 2층 3호 거주자 수를 구할 수 있을 것이다.

 

k층 n호의 거주자 수가 k-1층 1호~n호 거주자 수의 합이므로, k층 n-1호의 거주자 수는 k-1층 1호~n-1호 거주자 수의 합이라는 점에 주목하자. k층 n호 값을 알기 위해 필요한 값들 중 k-1층 n호 거주자 수를 제외하고 이미 모든 값이 구해져있는 셈이다. k층 n호 보다 먼저 계산된 k층 n-1호 값에 k-1층 n호 값을 더하는 한번의 연산만으로 거주자 수를 알 수 있다. 당연히 k-1층 n-1호의 거주자 수는 똑같은 방식으로 이전에 계산된 k층 n-2호의 값을 사용해 구할 수 있다.

 

k층 n호 거주자 수 = k-1의 1~n호 거주자 수
k층 n호 거주자 수 = k층 n-1호 거주자 수 + k-1층 n호 거주자 수

 

참고로, 위의 그림에서 알 수 있듯이 k층 n호의 값을 알기 위해 사용되는 값은 0층~k층 1호~n호 값 뿐이다.

파란색 : 구하려는 값, 빨간색 : 필요한 값들

 

이제 호수가 최대 14라는 점을 참고해서 크기 14의 int 배열을 선언해 하나의 층으로 여겨 계산한다. 0층의 호들의 값은 알려줬으므로 1차원 배열의 모든 요소를 0~14까지 정수로 초기화해서 아래와 같은 모양으로 만들어준다.

 

이제 초기화된 1차원 배열을 k-1층 이라고 여기고 k층 각 호의 거주자 수를 계산한다. 배열을 k-1층 이라고 여기라 했으니 각 요소는 k-1층 i호 거주자 수가 된다.  [ k층 i호 값 = k층 i-1호 값 +  k-1층 i호 값 ] 연산에 사용되는 k층 i-1호 값은 해당 배열의 [i-1] 번째 요소 값이고, k-1층 i호 값은 아직 갱신되지 않은 [i]값. 즉, 자기자신이다. 자기자신에 arr[i-1] 값을 추가해서 누적하는 것.

arr[i] = arr[i-1] + arr[i]
→ arr[i] += arr[i-1]

위에서 호수는 1부터 시작한다 했으나, 0호가 존재하는 이유는 i호 값을 구하기 위해 i-1호 값을 참조하는 과정에서 인덱스가 0-1로 -1이 되는 것을 막기 위함이다. 즉, 1호 값을 계산하기 위한 더미 값(0)을 넣어둔 셈. 참고로 [0]~[14] 까지 모든 요소를 초기화 해뒀지만 실제로 계산에 사용되는 값은 [0]~[n] 값 뿐이다. 나머지 값은 초기화 값 그대로 변하지 않고 참조되지도 않는다.

0층은 초기화로 값을 구했으니, 1층~k층 까지 각 배열을 갱신해나간 뒤, 마지막으로 갱신된 arr[n] 값을 출력한다.

자세한 과정은 아래 그림을 참고.

2층 3호 거주자 수를 구하는 과정 (k : 2, n : 3)