글 읽기 - 반례가 절박합니다...

dladydwo123 5년 전 0

최대한 일반화 시켜서 짜본다고 짜봤습니다.

논리는 X = 5 * K + A이고

A은 무조건 1센트로 만들어야 하는 수 로 생각했습니다.

동전을 최대한 많이 사용해야 함으로, 1센트 최대갯수 반복 -> 5센트 최대 갯수 반복 -> 10센트 최대 갯수 반복으로 코드를 구성했습니다.

#include<iostream>
//#pragma warning(disable:4996)
using namespace std;

int info[4];
int N;

int main() {
	//freopen("input.txt", "r", stdin);
	cin >> N;
	for (int i = 0; i < 4; i++) {
		cin >> info[i];
	}

	int n = N % 10; 
	if (n >= 5) {
		n -= 5;
	}

	if (info[0] < n) {
		cout << "0 0 0 0";
		return 0;
	}
	//n개의 1센트는 최소한 필요하다.

	int l = (info[0] - n) / 5;
	for(int h = l; h >= 0; h--){
		int remain = N - n - 5 * h;

		for (int i = info[1]; i >= 0; i--) {
			if (5 * i > remain)
				continue;

			for (int j = info[2]; j >= 0; j--) {
				if (5 * i + 10 * j > remain)
					continue;

				int ret = remain - 5 * i - 10 * j;
				if (ret % 25 == 0) {
					int need = ret / 25;

					if (need <= info[3]) {
						cout << n + 5 * h << ' ' << i << ' ' << j << ' ' << need;
						return 0;
					}
				}
				else
					continue;
			}
		}
	}

	cout << "0 0 0 0";
	return 0;
}

yukariko 5년 전 1

작은 동전부터 최대로 만드려 하면 오히려 작은 동전을 적게 사용했을때 답이 더 커지는 경우가 있습니다.

이 문제는 동적 계획법으로 해결되는 문제입니다.

dladydwo123 5년 전 1

큰 동전들은, 작은동전들이 여유분이 있다고 할때 ,항상 작은 동전들의 조합으로 표현되는데

작은동전을 적게 사용했을때 답이 더 커지는 경우가 있나요?

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

문제

문제

출처

ICPC

반례가 절박합니다...

dladydwo123 5년 전 0

yukariko 5년 전 1

dladydwo123 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말