글 읽기 - 크리스마스 트리

alohajihwan 6년 전 0

제 코드에서 무엇이 틀렸는지 모르겠습니다..

도움 부탁드립니다..

#include<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<string.h>
#include<stack>
using namespace std;
#define INF 999999999
#define ll long long int 

int N,A,B,C;
ll dp[11][101][101][101];
ll solve(int n, int a, int b, int c)
{
	if (n == 0) return 1;
	//if (a == 0 && b == 0 && c == 0) return 0;
	ll & ret = dp[n][a][b][c];
	if (ret != -1) return ret;
	ret = 0;
	//한색
	if (a >= n) ret += solve(n - 1, a - n, b, c);
	if (b >= n) ret += solve(n - 1, a, b - n, c);
	if (c >= n) ret += solve(n - 1, a, b, c - n);
	//두색
	if (n % 2 == 0) {
		if (a >= n / 2 && b >= n / 2)
			ret += solve(n - 1, a - n / 2, b - n / 2, c)*2;

		if (a >= n / 2 && c >= n / 2)
			ret += solve(n - 1, a - n / 2, b, c - n / 2)*2;

		if (c >= n / 2 && b >= n / 2)
			ret += solve(n - 1, a, b - n / 2, c - n / 2)*2;
	}
	//삼색
	if (n % 3 == 0) {
		if (a >= n / 3 && b >= n / 3 && c >= n / 3)
			ret += solve(n - 1, a - n / 3, b - n / 3, c - n / 3) * 6;
	}
	return ret;
}
int main()
{
	cin >> N >> A >> B >> C;
	memset(dp, -1, sizeof(dp));
	cout << solve(N, A, B, C) << endl;
}

sksdong1 6년 전 1

저도 아직 맞추진 못했지만 생각난게 *2 , *6이 고정된게 원인 같네요,

n 단계 레벨에서 두색, 또는 삼색으로 나열할 수 있는 모든 경우를 구현해줘야하는데, 예를들어

4단계이면 aabb를 배열할 때

aabb

abab

abba

baab

baba

bbaa

6가지가 있기 때문에 *2가 아닌 *6이 되어야할거 같은데

따라서 단계별로 곱하는 규칙을 찾으시면 될 것 같은데용

alohajihwan 6년 전 0

헐... 그러네요.. 전혀 생각도 못했습니다..ㅠㅠㅠ

답변 정말 감사드립니다^^

sksdong1 6년 전 1

저도 덕분에 맞췄네요 규칙 찾으시면 AC나옵니당.

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

문제

문제

출처

ICPC

크리스마스 트리

alohajihwan 6년 전 0

sksdong1 6년 전 1

alohajihwan 6년 전 0

sksdong1 6년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말