BOJ#1670 정상 회담2

BOJ#1670 정상 회담2

* 문제

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

* 풀이

Dynamic Programming 문제입니다. 동적계획법은 복잡한 문제를 하위 문제로 나누어 푸는 것을 말합니다.

이 문제에서는 그림을 그려보면 이해하기 쉽습니다.

예를 들어 N = 6일 때, 아래 3가지 경우의 합을 구하면 되겠습니다.

1) 0번째 사람과 1번째 사람이 악수하는 경우

dp[6] += dp[0] + dp[4]

(한쪽 구역은 0명, 다른 구역은 4명)

2) 0번째 사람과 3번째 사람이 악수하는 경우

dp[6] += dp[2] + dp[2]

(한쪽 구역은 2명, 다른 구역은 2명)

3) 0번째 사람과 5번째 사람이 악수하는 경우

dp[6] += dp[4] + dp[0]

(한쪽 구역은 4명, 다른 구역은 0명)

주의할 점

1. int가 아닌 long타입을 써야합니다.

2. 두 하위 문제로 구분한 이후 구한 두 값을 더하는 것이 아니라 곱해야 합니다.(경우의 수)

3. Top-down 재귀 형식으로 구현 시 재귀 호출이 많아져 시간이 오래걸립니다.

bottom-up 형식으로 구현을 추천합니다.

---

* 나의 코드

https://github.com/stack07142/BOJ/blob/master/BOJ%231670_Conference/src/Main.java

1. Bottom-up DP (120ms)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * BOJ#1670 정상회담2
 * https://www.acmicpc.net/problem/1670
 */

public class Main {

    static final int MOD = 987654321;
    static long[] dp = new long[10005];

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

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

        int N = Integer.parseInt(br.readLine());

        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= N; i += 2) {

            for (int j = 1; j < i; j += 2) {

                dp[i] += dp[j-1] * dp[i - (j + 1)];
                dp[i] %= MOD;
            }
        }

        System.out.println(dp[N]);
    }
}

2. Top-down 재귀 DP (120ms)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * BOJ#1670 정상회담2
 * https://www.acmicpc.net/problem/1670
 */

public class Main {

    static final int MOD = 987654321;
    static long[] dp = new long[10005];

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

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

        int N = Integer.parseInt(br.readLine());

        System.out.println(solve(N));
    }

    static long solve(int N) {

        if (N == 0) {

            return 1;
        }

        if (N == 2) {

            return dp[2] = 1;
        }

        if (dp[N] > 0) {

            return dp[N];
        }

        long ret = 0;

        for (int i = 1; i < N; i += 2) {

            ret += solve(i - 1) * solve(N - (i + 1));
            ret %= MOD;
        }

        return dp[N] = ret;
    }
}