[코딩테스트 챌린지] 백준 2775 부녀회장이 될테야 (java)

문제

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

 

문제 탐색하기

1. DP 설계하기

DP 알고리즘을 구현하는 방식은 Top-Down(하향식) 방식과 Bottom-Up(상향식) 방식이 존재합니다. 이 전 게시글인 피보나치 수2 문제를 풀때는 상향식 방식으로 반복문을 활용하여 문제를 풀었습니다. 이 문제는 Top-Down 방식으로 재귀함수를 구현하여 문제를 풀어보려 합니다.

 

* 백준 2748번 피보나치 수2 풀이 게시글

https://coding-babo.tistory.com/139

[코딩테스트 챌린지] 백준 2748 피보나치 수 2

 

Top-down(하향식) 방식이란?

상위 문제를 해결하기 위해 하위 문제를 재귀적으로 호출합니다. 하위 문제 해결을 반복하며 상위 문제까지 해결하는 방식입니다. 이 때 해결해놓은 하위 문제를 저장해두어야 불필요한 연산을 감소시킬 수 있기에 이때 Memoization이 사용됩니다.

 

Memoization(메모이제이션) 이란?

메모이제이션은 한 번 계산한 결과를 메모리 공간에 저장하는 기법입니다. 즉, 이미 풀린 하위 문제를 다시 풀지 않고 재활용하는 것을 뜻합니다. 

 

즉, 메모이제이션을 활용한 DP 설계는 메모리에 값이 이미 저장되어있는 경우에는 저장된 값을 사용하고 없을 경우에는 재귀 호출을 하는 식으로 구현하면 됩니다.

 

2. 초기값 세팅하기

input 값의 범위 1 <= k,n <= 14아파트 0층의 i호는 i명이 산다는 조건이 있습니다. 0층의 1호부터 14호까지의 인원수를 조건에 맞게 저장합니다.또 규칙을 따르면 아파트 각 층의 0호는 1명만 거주하게 되어있습니다. 따라서 이 값도 초기값으로 배열에 저장합니다.

 

3. 재귀함수 설계하기

주어진 아파트 호실을 통해 몇명이 살고있는지 구하는 재귀함수를 설계하려 합니다.

3층 [1][4][10]
2층 [1][3][6]
1층 [1][2][3]
0층 1호 2호 3호

 

0층부터 3층까지 살고있는 사람 수를 나타내보았습니다.

이 도면을 보면 '3층 3호에 살고있는 사람 수 = 3층 2호 사람 수 + 2층 3호 사람 수' 임을 알 수 있습니다.

즉, 왼쪽 방과 아래쪽 방의 사람 수를 알게된다면 원하는 호실의 사람 수를 알 수 있다는 뜻입니다.

 

왼쪽 방 위치 배열에 저장된 값이 없을 경우 재귀호출을 진행하고 저장된 값이 있을 경우 그 수를 변수에 저장합니다.

아래쪽 방도 마찬가지로 해당 위치에 저장된 값이 없을 경우 재귀호출을 진행하고 저장된 값이 있을 경우 그 수를 변수에 저장합니다.

이렇게 재귀함수를 설계하게 되면 중복 연산은 피하고 원하는 값을 구할 수 있습니다.

 

코드 설계하기

1. Test Case 수 입력
2. 아파트 배열 생성
3. 아파트 배열 초기값 입력, 0층과 각 층의 1호실 초기값 세팅
4. k층 n호에 사는 사람 수를 구하는 메소드 호출
   1. 왼쪽 방 사람 수가 구해지지 않았을 경우 같은 메소드 호출, 구해졌을 경우 왼쪽 방 사람 수를 변수에 저장
   2. 아래쪽 방 사람 수가 구해지지 않았을 경우 같은 메소드 호출, 구해졌을 경우 아래쪽 방 사람 수를 변수에 저장
   3. 왼쪽 방과 아래쪽 방 사람 수의 합을 리턴
5. 각 케이스에 맞는 호실의 인원수를 출력

 

정답 코드

package backjun;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class Apart {

    public static void main(String[] args) throws IOException {

        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        // 1. Test Case 수 입력
        int T = Integer.parseInt(reader.readLine());

        // 2. 아파트 배열 생성
        int[][] apart = new int[15][14];

        // 3. 아파트 배열 초기값 입력
        for(int i=0; i<14; i++){
            apart[0][i] = i+1;
            apart[i+1][0] = 1;
        }

        List<Integer> list = new ArrayList<>();
        for(int i=0; i<T; i++){
            int k = Integer.parseInt(reader.readLine()); // # k층 입력
            int n = Integer.parseInt(reader.readLine()); // # n호 입력

            // # k층 n호에 사는 사람 수를 구하는 메소드 호출
            list.add(peopleCount(k, n-1, apart));
        }

        // 5. 출력
        for(long i : list){
            System.out.println(i);
        }
    }

    /** 4. k층 n호에 사는 사람 수를 구하는 메소드 **/
    private static int peopleCount(int k, int n, int[][] apart){

        int leftRoom = 0; // # 왼쪽 방 사람 수 저장하는 변수
        int belowRoom = 0; // # 아래 방 사람 수 저장하는 변수

        if(n == 0) return apart[k][0];

        /**
         * 4-1. 왼쪽 방 사람 수가 구해지지 않았을 경우 재귀 함수 호출
         * 사람 수가 구해졌을 경우 변수에 저장
         */
        if(apart[k][n-1] == 0){
            leftRoom = peopleCount(k, n-1, apart);
        }else{
            leftRoom = apart[k][n-1];
        }

        /**
         * 4-2. 아래 방 사람 수가 구해지지 않았을 경우 재귀 함수 호출
         * 사람 수가 구해졌을 경우 변수에 저장
         */
        if(apart[k-1][n] == 0) {
            belowRoom = peopleCount(k-1, n, apart);
        }else{
            belowRoom = apart[k-1][n];
        }

        return leftRoom + belowRoom; // 4-3. 왼쪽 방과 아래 방의 사람 수 합한 값 return
    }
}