[Baekjoon] 정상회담 2(BOJ 1670)

👀 문제 설명

문제

여러 개의 소국가로 나뉘어져 있었던 A국을 다시 하나의 국가로 합치기 위해 각 소국가의 대표 N명이 원탁에 모였다.

각 대표는 미리 원탁의 자리를 배정받았다. 회의를 시작하기 전에 일단 서로 악수를 하려고 한다. 각 대표는 한 사람과만 악수할수 있고, 모든 악수는 동시에 일어난다. 이때, 어떤 사람의 팔도 교차하지 않았을 때 완벽하게 악수했다고 한다.

N이 주어지면 완벽하게 악수하는 경우의 수를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 정상 회담에 참가한 사람의 수 N이 주어진다. 이 값은 10,000보다 작거나 같은 짝수이다.

 

출력

완벽한 악수의 경우의 수를 987654321로 나눈 나머지를 출력한다.

 

예제 입력 1

4

 

예제 출력 1

2

 

힌트

✍🏻풀이

분류가 수학이라 수학으로 푸는 건줄 알았는데 알고 보니까 DP였다..! DP 어려워 ..

 

 

상수 선언

const long MOD : 987654321 상수 선언

 

필요한 변수

long dp[10000] : Dynamic Programming 값을 저장하기 위한 배열

 

알고리즘

1. i는 4부터 N까지 for문을 돌린다. (이 때, i는 2씩 증가해야 한다.) - 홀수면 악수하는 인원이 딱 나눠떨어지지 않기 때문에

2. 1의 for문 안에서 다시 for문을 사용한다. 변수 j는 0부터 i - 2까지이고, 2씩 증가

3. 2의 for문 안에서 dp[i]는 기존 dp[i]의 값에 dp[j] * dp[i - j - 2]를 한 후 MOD로 나눈 값이다.

-> 3 설명

만약 8명이 악수를 한다고 가정한다면, 총 4가지의 경우의 수가 생긴다.

1. 0과 1이 악수하는 경우

이 경우는 영역이 나눠지지 않으므로 0과 1이 악수하는 경우 dp[0]과 나머지 6명이 악수하는 경우 dp[6]을 곱한 값이다.

 

2. 0과 3이 악수하는 경우

이 경우 위에 2명, 아래 4명이 악수하는 경우의 수 두 가지를 곱한 값. 즉, dp[2] * dp[4]이다.

 

3. 0과 5가 악수하는 경우

이 경우 위 4명, 아래 2명이 악수하는 경우의 수 두 가지를 곱한 값. 즉, dp[4] * dp[2]이다.

 

4. 0과 7이 악수하는 경우

이 경우도 1과 같이 영역이 나눠지지 않으므로 dp[6] * dp[0]이다.

 

1~4까지의 경우의 수를 더해주면 총 경우의 수가 나온다.

 

코드

//
//  BOJ_1670.cpp
//  Algorithm
//
//  Created by 조수민 on 2020/06/23.
//  Copyright © 2020 조수민. All rights reserved.
//
//  정상 회담 2(https://www.acmicpc.net/problem/1670)

#include <stdio.h>
#include <iostream>

using namespace std;

const long MOD = 987654321;
long dp[10000];

long getNumber(int N)
{
    dp[0] = dp[2] = 1; // 0명일 때와 2명일 때 악수하는 경우의 수는 1번
    
    for (int i = 4; i <= N; i+=2) // 2씩 증가해야 한다. (홀수면 악수하는 인원이 딱 나누어 떨어지지 않는다.)
        for (int j = 0; j <= i - 2; j+= 2) // dp값 구하기
        {
            dp[i] += dp[j] * dp[i - j - 2];
            dp[i] %= MOD;
        }
    
    return dp[N];
}

int main()
{
    int N;
    cin >> N; // N 입력 받기
    
    cout << getNumber(N) << endl; // 출력
    
    return 0;
}

[참고] https://bcp0109.tistory.com/52?category=847904