BOJ 1670번 : 정상 회담 2

오랜만에 골드 문제!

처음에 만들었던 수식이 완벽한줄 알았지만.. 3번쯤 틀리고서야 수식이 잘못 됬다는걸 알았다.

열심히 공부하자... ㅠㅜ 

게다가 MOD 를 출력하는 건지 몰라서 2번쯤 또 틀렸다..헤헤...

문제좀 끝까지 읽자.... ㅠ

 

<Solution>

경우의 수를 잘 따져야 하는 문제이다.

 

이 문제의 경우, 한 사람을 기준으로 두고 생각하면 편하다.

 

6명일 경우를 예시로 들어보자.

이 그림의 경우에서 6을 기준으로 보자.

6의 위치에서 악수가 가능한 사람은 1,3,5번 이다.

6과 1이 연결 되었을 경우에는 (2,3,4,5)가 각각 악수할 경우인 4명이 완전한 악수를 할 수 있는 경우의 수와 같다. 

 

6과 3이 연결 되었을 경우에는 (1,2), (4,5)가 각각 연결된 경우인 2명이 완전한 악수를 할 수 있는 경우의 수와 같다. 물론 곱을 해야한다.

 

이와 같은 방식으로 생각을 할수 있다.

 

 

 

 

 

 

 

 

이번엔 8명일 경우 한사람을 기준으로 생각해 보면 아래 그림과 같다.

1번 사람이 

 

 

 

사람이 6명일 경우와 다른점은 선의 갯수가 짝수개 라는 점이다.

이처럼 4,8,12명일 경우에는 한사람 기준에서 연결 될 수 있는 사람의 수는 짝수이지만, 6,10명일 경우에는 홀수 이다.

이 경우를 판단하려면 ((n/2)-1)%2 가 0인지를 판단하면 된다.

 

 

 

 

 

위 설명들을 바탕으로 아래 예시처럼 수식을 세울 수 있다.

계산의 편의를 위해 dp[0] = 1 로 계산하였다.

 

1) 한 사람 기준에서 악수 할 수 있는 사람수가 짝수 일 경우 ((n/2)-1)%2 != 0

   예) 8명

2) 한 사람 기준에서 악수 할 수 있는 사람수가 홀수 일 경우 ((n/2)-1)%2 == 0

   예) 10명

위처럼 2가지 경우로 나누어 구현하면 되고, 각 곱하기, 나누기 마다 MOD 처리를 해주어야 한다.

또한! 변수형을 long long 으로 해주어야한다.

 

<소스코드>

#include<iostream>
#include<vector>
#define MOD 987654321
using namespace std;
void Solve() {
    int n;
    cin >> n;
    vector<long long> v(n+3,0);
    v[0] = v[2] = 1;
    
    for (int i = 4;i<=n; i+=2) {
        int count = 0;
        long long temp = 0;
        if (!((i / 2 - 1) % 2)) {
            temp += (v[(i - 2) / 2] % MOD * v[(i - 2) / 2] % MOD) % MOD;
            for (int x = i - 2; count != (i-2)/4 ;x-=2) {
                temp += (2 * v[x] % MOD * v[i - 2 - x] % MOD) % MOD;
                count++;
            }
        }
        else {
            for (int x = i - 2; count != i/4 ; x -= 2) {
                temp += (2 * v[x] % MOD * v[i - 2 - x] % MOD) % MOD;
                count++;
            }
        }
        v[i] = temp % MOD;
    }
    cout << v[n] << endl;
}
int main() {
    Solve();
}

 

<문제>

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

1670번: 정상 회담 2