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

#수학

앞서 푼 벌집과 위 문제는 규칙을 찾아서 주어진 값을 기준으로 앞으로 채울 값을 구해줘야 합니다. 따라서 규칙성을 찾는 비중이 문제해결에 크게 작용합니다. 해당 문제는 두 방식으로 풀 수 있습니다. 1) 2차원 배열 int[][]과 for문을 이용해서 array [int : 층][int : 호수]를 채워주는 경우, 2) 재귀 함수(Recursion)을 이용하는 방법입니다.

1. 2차원 배열과 for문 이용한 풀이

재귀 함수로 치면 기저식을 만들어줍니다. 0층에 사는 사람의 수는 1~14로 문제에서 주어졌기 때문에 people[0][i]를 1,2,3....,14로 채웁니다. 그리고 a층 b호의 세입자 수는 (a-1)층의 1호에서 b호까지 세입자 합과 같기 때문에 1호에 사는 사람은 고정 1명입니다. 0층 1호가 1명이기 때문이죠. people[i][1]을 1로 채워줍니다. 

기저식이 완성됐으면 규칙을 찾아 반복문을 만들어줍니다. 비슷한 문제를 풀다보면 순환식이 눈에 들어옵니다. a층 b -1호의 세입자 수와 a-1층 b호의 세입자 수를 더하면 a층 b호 세입자가 나옵니다. 이를 수식으로 나타내면 f(a, b) = f(a, b-1) + f(a-1, b) 로 간단히 표현할 수 있습니다.

1번 풀이는 배열을 활용했기 때문에 1층 2호부터 차례로 반복문을 돌며 세입자 수를 저장해줍니다.(1호는 1명으로 고정)

public class Apartment_2775_ex {
 
    static int r;
    static int a;
    static int b;
    static int[][] people;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        r = Integer.parseInt(br.readLine());
 
        people = new int[15][15];
 
        for (int i = 1; i < 15; i++) {
            people[0][i] = i;
            people[i][1] = 1;
        }
 
        for (int i = 0; i < r; i++) {
            a = Integer.parseInt(br.readLine());
            b = Integer.parseInt(br.readLine());
 
            for (int j = 1; j < 15; j++) {
                for (int k = 2; k < 15; k++) {
                    people[j][k] = people[j][k-1] + people[j-1][k];
                }
            }
            sb.append(people[a][b] + "\n");
        }
        System.out.println(sb);
 
    }
 
}
 

 

---

2. 재귀 함수(Recursion)

재귀 함수는 알고리즘 코드가 간단하고 보기 편한 장점이 있지만 메모리나 시간 복잡도가 높은 단점을 가지고 있습니다. 알고리즘 문제를 풀다보면 재귀를 이용해야 될 때가 생기고 DP(Dynamic Programming) 동적 계획법에서도 쓰이기 때문에 알아둘 필요가 있습니다. 

보시다시피 같은 문제의 풀이인데 코드 간결성이 확연히 차이 납니다. 기저식은 a층 b호수 일 때 1호면 1을 반환해주고, 0이면 b를 가공없이 그대로 반환하도록 짜여 있습니다.

public class Apartment_2775_ex2 {
 
    static int r;
    static int a;
    static int b;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        r = Integer.parseInt(br.readLine());
 
 
        for (int i = 0; i < r; i++) {
            a = Integer.parseInt(br.readLine());
            b = Integer.parseInt(br.readLine());
 
            System.out.println(house(a,b));
        }
 
    }
 
    public static int house(int a, int b) {
        if (b == 1)
            return 1;
        if (a == 0)
            return b;
        else
            return house(a-1, b) + house(a, b-1);
 
    }
 
}