글 읽기 - 1398 탐욕법으로 풀면 안되나요?

psychobabo 8년 전 0

전체 동전을 배열로 구성해서 (ex, long coins[] = {1,10, 25, 100, 1000, 2500, 10000, ....}

정렬한 후, 아래 소스와 같이 탐욕법으로 구성해 봤는데 자꾸 틀렸습니다가 나오네요..

제가 검토하지 못한 테스트 케이스가 있는걸까요? 아니면 문제를 제대로 이해 못한걸까요?

            long num = Long.parseLong( br.readLine() );
            long total = 0;
			while ( num != 0 ) {
				for ( int j = 22; j >=0; j-- ) {
					if(num >= coins[j]) {
						total++;
						num -= coins[j];
						break;
					}
				}
			}

indioindio 8년 전 1

25가 10의 배수가 아니어서 무조건 적용하기에는 어렵지 않을까 싶네요.

amugeona 8년 전 3

작성자님의 방법대로면 34 가 반례가 생깁니다. 34는 10 * 3 + 1 * 4 로 7개를 쓰면 되는데, 25 * 1 + 1 * 9 를 쓰게 되면 10개를 써야합니다.

이런 경우도 잘 처리할 수 있도록 탐욕 알고리즘을 사용하시면 됩니다. :)

psychobabo 8년 전 0

아 그렇군요! 반례 감사합니다~~ 한번 더 짜봐야겠어요 ^^

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

문제

문제

출처

ICPC

1398 탐욕법으로 풀면 안되나요?

psychobabo 8년 전 0

indioindio 8년 전 1

amugeona 8년 전 3

psychobabo 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말