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

BOJ - [2775] 부녀회장이 될테야

---

🖍 주어진 조건에 맞게 입력된 k층 n호에 사는 인원을 구한 뒤 출력하는 문제
(link) 2775 부녀회장이 될테야

---

[풀이 과정]

배열을 사용한 다이나믹 프로그래밍(DP) 문제.

다이나믹 프로그래밍이 뭔지 간단하게 설명하자면, 이전에 구해두었던 값은 다시 계산할 필요 없이 이전의 값을 활용할 수 있게끔 하는 기법이다. 

 

일단.. 문제를 읽으니 단번에 이해가 안된다. 무슨 내용인지 먼저 설명하겠다.

0층부터 14층, 1호부터 14호까지 있는 아파트다.
0층에 사는 사람은 1호에 1명, 2호에 2명.... 14호에 14명이 산다.
1층 부터는 아래 층 호수까지의 사람들을 합산한 인원이 해당 호수에 살아야 한다.

말로 설명하면 무슨 말인지 이해가 잘 안되는데 순서대로 적어보자면,

2층 : 1, 4, 10, 20 ...

1층 : 1, 3, 6, 10 ...

0층 : 1, 2, 3, 4 ...

이런식으로 살고 있는 것이다.

(가끔 이렇게 어이가 없는 문제를 보면 웃기다. 그리고 대체 부녀회장이랑은 무슨 연관이 있는가)

 

일단 아파트 전체를 2차원 배열로 보기로 했다. 최대 입력값이 14이므로 필요한 연산만 해주는 것 보다 2차원 배열에 답들을 우선 넣어놓고 찾아서 출력하는 식으로 풀어볼까 한다.

그런데 2차원 배열을 선언할 때 15x15 배열을 만들어 줄 것이다. 층수는 0 ~ 14이기 때문에 15개인게 당연하고, 호수는 1 ~ 14인데 왜 15개를 만드는가?

이유는 0이라는 데이터가 필요하기 때문이다. (물론 필요 없게 짤 수도 있지만, 0이 있는 편이 조금 더 편할듯)

더 자세히 설명해보자면,

(예시이기 때문에 이만큼만 다뤄보도록 하겠다.)

2차원 배열을 만들고 n호에 사는 사람들을 나열해보면 다음과 같은 사실을 알 수 있다.

k층 n호에 사는 사람은 k층 n-1호에 사는 사람과 k-1층 n호에 사는 사람을 합한 인원과 같다.

(즉, 빨간 숫자들의 합은 파란 숫자가 된다)

이러한 규칙을 이용하여 배열을 채워나갈 수 있다.

 

그런데 이 규칙을 이용하려면 1호에 사는 1명을 채울 때도 n-1호의 인원이 필요하다. 그러나 n-1호가 존재하지 않으므로 임의로 앞에 0값을 만들어주기 위해 배열의 크기를 한 칸 더 확보한 것이다.

2차원 배열을 돌기 위해 이중 for문을 사용할텐데, 두번째 반복문으로 들어가기전 배열[k][0]의 값을 0으로 설정한 후 [k][1]자리부터 위에서 말한 규칙을 사용하면 되겠다.

 

그러면 애초에 [k][0]을 1로 모두 초기화 해주고 그 다음부터 계산하면 되지 않나.. 싶은데
일단 15칸이어도 인덱스는 14까지니까 1부터 시작하면 보기가 더 편하기도 해서 냅뒀다.

아무튼 이런 식으로 배열을 모두 채운 뒤 입력으로 들어오는 k층 n호의 배열에 접근해서 값을 알아내면 된다.

---

[Pseudocode]

1. 테스트 케이스 개수를 입력받을 변수 T 선언
2. 층과 호수를 입력받을 변수 k, n 선언
3. 아파트를 나타내는 2차원 배열 apart 선언
4. for i=0 부터 apart[0] 길이까지 반복
    5. apart[0][i] = i;
5. for i=0부터 apart 길이까지 반복
    7. apart[i][0] = 0;
    8. for j=0 부터 apart[i] 길이까지 반복
        9. apart[i][j] = apart[i][j-1] + apart[i-1][j]
10. for i=0 부터 T까지 반복
    11. k와 n 입력받기
    12. apart[k][n] 출력

---

[Code]

import java.util.*;

/**
 * 백준 2775번
 * 부녀회장이 될테야
 * 분류: 수학, 구현, 다이나믹 프로그래밍
 */
public class Problem4 {

    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int T = input.nextInt(); // 테스트 케이스 개수
        int k,n; // k층, n호 테스트 케이스 저장 변수
        int[][] apart = new int[15][15]; // 아파트 인원을 저장할 2차원 배열 선언

        // 0층 채우기 (i=1,2,3...)
        for(int i=0 ; i<apart[0].length ; i++) {
            apart[0][i] = i;
        }

        // 1층 ~ 14층 채우기
        for(int i=1 ; i<apart.length ; i++) {
            apart[i][0] = 0;
            for(int j=1 ; j<apart[i].length ; j++) {
                apart[i][j] = apart[i][j-1] + apart[i-1][j]; // k층 n호 인원 = (k층 n-1호 + k-1층 n호) 인원 
            }
        }

        // 인원 수가 채워진 2차원 배열 출력
        for(int i=0 ; i<T ; i++) {
            k = input.nextInt();
            n = input.nextInt();
            System.out.println(apart[k][n]);
        }
        input.close();
    }
}

---

[Result]

---

(2021.07.15 풀이분)

이 문제는 최근 알고리즘 스터디를 하면서 또 한번 풀었던 문제다.

그만큼 다이나믹 프로그래밍은 중요한 개념이므로 쉬운 문제부터 시작해서 확실히 알아두는 게 좋다.

(지금 살짝 고쳐서 14x14 배열로 해보려고 했는데 자꾸 틀린다. DP의 개념은 알았으니 나중에 시도해보겠음)