글 읽기 - 동전문제 어디서 틀린걸까요?

lyzqm 6년 전 0

동전종류가 23개밖에 안되서 브루트포스로 풀었는데 틀리네요.

test case

34 - 7

59 - 11

74 - 8

3434 - 14

다 맞는거같은데 어디서 틀렸을까요?

#include <cstdio>
#define INF 2222222222222222
typedef unsigned long long ull;
ull dp[24];
ull print = INF;
void solve(ull C, ull ans){
	if (C < 0) return;
	if (C == 0) {
		print = print > ans ? ans : print;
		return;
	}
	for (int n = 23; n >= 1; n--){
		if (dp[n] > C) continue;
		ull modul = C / dp[n];

		if (modul > 0){
			if (ans + modul < print)
				solve(C - (modul * dp[n]), ans + modul);
		}
	}
}
int main(){
	ull T;
	int cnt = 1;
	scanf("%llu", &T);

	dp[1] = 1;
	while (1){
		if (cnt % 3 == 1)dp[cnt + 1] = dp[cnt] * 10;
		else if (cnt % 3 == 2) dp[cnt + 1] = dp[cnt] * (double) 2.5;
		else dp[cnt + 1] = dp[cnt] * 4;
		if (dp[++cnt] > 1e15) break;
	}
	while (T--){
		int ans = 0;
		ull C;
		scanf("%llu", &C);

		print = INF;
		solve(C, 0);
		printf("%llu\n", print);
	}
	
	return 0;
}

jpseo99 2년 전 1

59 -> 25*1, 10*3, 1*4로 8개 입니다.

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

문제

문제

출처

ICPC

동전문제 어디서 틀린걸까요?

lyzqm 6년 전 0

jpseo99 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말