글 읽기 - 제가 생각한 방법이 왜 틀렸는지, 반례가 있는지 궁금합니다

kimjin108 3년 전 0

제가 dp는 아니지만 사진과 같은 논리로 문제를 풀었는데 이 논리가 뭐가 잘못된건지 알려주세요! 구글링해보니까 피보나치랑 똑같이 풀면된다하는데 저는 이 방법도 맞다고 생각해서요ㅜㅜ

#include<iostream>
//ong long array[1001];
unsigned long long permutation(int,int,int);
int main() {
	unsigned long long result=0;
	int a;
	scanf("%d", &a);
	int remain;//나머지
	int share;//몫
	unsigned long long sum=0;
	if (a == 1)
		result = 1;
	if (a == 2)
		result = 2;
	if (a >= 3) {
		share = a / 2;
		remain = a % 2;
		for (int i = 0; i <= share; i++) {
			int vertical = a - (i*2);
			//printf("%d\n", vertical);
			int horizon = i;
			//printf("%d\n", horizon);
			int whole = vertical + horizon;
			//printf("%d전체\n", whole);
			unsigned long long temp = permutation(whole,horizon,vertical);
			//printf("%d탬프\n", temp);
			sum += temp;
			//printf("\n");
		}
		//printf("%lld", sum);
		result = sum;
	}
	sum = result % 10007;
	printf("%d", sum);
	return 0;
}

unsigned long long permutation(int whole, int h, int v) {
	unsigned long long result=1;
	int a, b;
	if (h > v) {
		a = h;
		b = v;
	}
	else if(h <= v) {
		a = v;
		b = h;
	}
	
	for (int i = whole; i > a; i--) {
		result *= i;
	}
	//printf("%d훌까지만 \n", result);

	if (b != 0) {
		for (int j = b; j > 0; j--) {
			result =result/ j;
			//printf("%d 중간과정 \n", result);

		}
	}
	//printf("%d마지막 훌 \n", result);

	return result;
}

wjdclgns12 3년 전 0

중간 계산 결과가 unsigned long long 범위를 넘어갈 수 있습니다.

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

문제

문제

출처

ICPC

제가 생각한 방법이 왜 틀렸는지, 반례가 있는지 궁금합니다

kimjin108 3년 전 0

wjdclgns12 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말