[Java 코딩테스트] 백준 2775 부녀회장이 될테야 / Dynamic Programming

오늘은 백준 2775번 부녀회장이 될테야 풀이를 할 예정이다. 그간 이런저런 일이 많아서 블로그에 소홀했는데,, 여튼! 시작해보자

---

바로 본론으로 들어가서,,

a층 b호에 살려면 자신의 아래(a-1)층의 1호부터 b호까지 사람들 수의 합만큼 사람들을 데려와 살야아 한다. 이 때, 0층 N호에는 총 N명이 산다.
→ 0층 1호에는 1명, 2호에는 2명, ..., 14호에는 14명 이 산다.
→ 1층 3호에 살려면 6명, 2층 3호에 살려면 10명을 데려와 살아야 한다.

문제에 따르면 1층 3호에 살려면 6명은 다음과 같이 구해진다

(1-1)층 1호~3호까지 사람의 수의 합 = 0층 1호 + 0층 2호 + 0층 3호 = 1 + 2 + 3 = 6명 이다.

마찬가지로, 2층 3호의 사람을 구해보면 (2-1층) 1호~3호까지 사람 수의 합 = 1층 1호 + 1층 2호 + 1층 3호 = 1 + 3 + 6 = 10명

subtree가 반복되는 구조다.

잘 보면, subtree가 반복되는걸 확인할 수 있다. 만약 3층 4호, 5층 6호 ... 로 확장해 나갈수록, k-1, k-2, k-3, ... (k-m >= 0)이 반복되고 이에 대응하는 n호에 대한 사람 수도 subtree에서 반복되어 나타날 것이다. (만약 머리에 안그려진다면, 직접 그려서 확인하는걸 추천한다.)

subtree가 반복될 때 우리는 Dynamic Programming을 통해 쉽게 해당 문제를 풀 수 있다. 층에 대한 사람 수를 결정해 놓고, 해당 호수를 출력하면 문제 풀이는 끝이난다.

→0층 1호에는 1명, 2호에는 2명, ..., 14호에는 14명 이 산다.

위 조건에 맞게, 1호~14호 까지는 1~14의 값을 넣어주고, 이후 층 부터 (k-1)층 n호에 대한 사람 수를 불러와 더해주면 된다.

문제 풀이를 위해 1차원 배열을 선언하고, 14개씩 끊어서 하나의 층을 표현할 예정이다.

        for(int i = 14; i < rooms.length; i++){
            int floor = i / 14;
            int number = (i % 14) + 1;
            int underFloor = floor-1;
            int underValue = 0;
            for(int j = 0; j < number; j++){
                underValue += rooms[underFloor * 14 + j];
            }
            rooms[i] = underValue;
        }

 

따라서 위의 표정을 보면, 층수는 ( i / 14 )의 값을 갖게 되고, 호수(number)는 ( i % 14 ) +1이 된다. 1을 더해준 이유는, 실제 호수는 0~13이 아닌 1~14호기 때문이다.

이후 아래층의 1호~number호 까지의 방에 살고있는 사람수 (underValue)를 계산한다. 이 때, underFloor*14인 경우는 1차원 배열로 선언했기 때문에, 바로 아래층의 위치를 구하기 위해 14를 곱해줘야 하기 때문이다.

 

---

최종 코드

public class Number2775 {
    public static void main(String[] args) throws IOException {
        int[] rooms = new int[15*14];
        for(int i = 0; i < 14; i++){
            rooms[i] = i+1;
        }
        for(int i = 14; i < rooms.length; i++){
            int floor = i / 14;
            int number = (i % 14) + 1;
            int underFloor = floor-1;
            int underValue = 0;
            for(int j = 0; j < number; j++){
                underValue += rooms[underFloor * 14 + j];
            }
            rooms[i] = underValue;
        }

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        while(T-- > 0){
            int k = Integer.parseInt(br.readLine());
            int n = Integer.parseInt(br.readLine());
            System.out.println(rooms[k * 14 + (n-1)]);
        }

    }
}

rooms의 배열이 14 * 14가 아닌 이유는, 아파트의 층수가 0층~14층까지 존재하기 때문에 총 15개의 층에 대해 연산해야 하기 때문이다.

결과는.. 정답!