글 읽기 - [힌트] 문제 접근 방법과 아이디어, 소스코드 입니다,

helios789789 3년 전 2

dp 로 해결할 수 있습니다.

num 명이 완벽하게 악수하는 경우의 수는

2명이 서로 악수하고, 나머지 num-2 명이 악수하는 경우
4명이 서로 악수하고, 나머지 num-4 명이 악수하는 경우
6명이 서로 악수하고, 나머지 num-6 명이 악수하는 경우
... 를 전부 더한 것

으로 분리할 수 있으며 각각의 부분을 계산하는 과정에서 겹치는 상태가 발생하므로 이를 메모이제이션 해줍니다.

cache[num] //num 명이 완벽하게 악수하는 경우의 수 로 메모이제이션 해줍니다.

덧셈 과정에서 오버플로우가 발생할 수 있으므로 long long 으로 해결해줍시다.

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
#include <map>
#include <stack>
#include <queue>
#include <list>
#include <string.h>
#include <math.h>
#include <cassert>
#include <limits.h>
#include <set>
#include <stdio.h>
#include <cctype>
#pragma warning(disable:4996)
using namespace std;

typedef unsigned long long ull;
typedef long long ll;

#define INF 987654321
#define MAX 10001
#define MOD 987654321

// x명 이서 완벽하게 악수하는 경우의 수를 메모이제이션
ll cache[MAX];

ll dp(ll num) {
	// 0 명 이나 2명이 완벽하게 악수하는 경우는 단 1가지
	if (num == 0 || num == 2)
		return 1;

	// 덧셈 중 int 형의 범위 인 경우 오버플로우 발생, long long 사용
	ll& ret = cache[num];
	
	if (ret != -1)
		return ret;

	ret = 0;

	// 현재 num 명이 완벽하게 악수하는 경우의 수는
	for (ll i = 2; i <= num; i += 2) {
		// 2명이 서로 악수하고, 나머지 num-2 명이 악수하는 경우
		// 4명이 서로 악수하고, 나머지 num-4 명이 악수하는 경우
		// 6명이 서로 악수하고, 나머지 num-6 명이 악수하는 경우
		// ... 를 전부 더한 것
		ret += dp(i - 2) * dp(num - i);
		ret %= MOD;
	}

	return ret % MOD;
}

void solve() {
	memset(cache, -1, sizeof(cache));
	cout << dp(n) << endl;
}

int main() {
	cin >> n;
	
	solve();

	return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

[힌트] 문제 접근 방법과 아이디어, 소스코드 입니다,

helios789789 3년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말