백준 1670번 : 정상회담 2 [자바]

 

 

🧫 문제 분석

 

✔️ 출처

정상회담 골드 3

 

📖 문제

 

조합을 이용한 DP 문제

 

이 문제의 경우 직접 손으로 그려봐야 명확히 이해가 가능하다. 

그렇지 않아도 그려볼 수 있는 문제는 손으로 직접 그려보면 이해도 잘되고 쉽게 문제의 해결방법을 얻을 수 있다. (나는 그랬다..)

 

문제를 봤다면 알듯이 인원이 짝수여야지만 가능하다. 

 

우선 임의의 한 점을 선택하고 양옆의 사람과 악수했을 때 경우의 수를 구한다.

임의의 1명 + 왼쪽 = 2명 , 이 2명을 제외한 나머지가 악수하는 경우의 수 :  dp[n-2] 

임의의 1명 + 오른쪽 = 2명 , 이 2명을 제외한 나머지가 악수하는 경우의 수 :  dp[n-2] 

 

여기에 더해 왼쪽 1명을 지나 2칸 뒤에 있는 사람과 악수하는 경우의 수 : dp[2] * dp[n-4] 

왜 이렇게 되는지 그려보자

 

n = 8일때 

이런식으로 2칸씩 뒤에 사람과 악수할때를 기준으로 양옆에 그룹이 생긴다. 이 해당 그룹들이 서로 악수하는 경우의 수를 구하면된다.

여기서는

dp[4] * dp[2] + dp[2] * dp[4] 가 된다. 

 

 

---

🔅 문제 풀이

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

public class Main {
    static final int MOD = 987654321;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        long[] dp = new long[10001];
        dp[2] = 1;
        dp[4] = 2;

        for (int i = 6; i <= n; i += 2) {
            // 1번 사람이 왼쪽사람과 악수하는 경우 (dp[i-2])
            // 1번 사람이 오른쪽 사람과 악수하는 경우 (dp[i-2])
            dp[i] = (dp[i - 2] * 2) % MOD;

            // 1번 사람이 나머지 팔이 교차하지 않는 위치에 있는 사람과 악수하는 경우의 수
            for (int j = i - 4; j >= 2; j -= 2) {
                dp[i] = (dp[i] + dp[j] * dp[i - j - 2]) % MOD;
            }
        }

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

 

 

 

❗ 오답노트 / 필요한 지식

1.