[백준] 11047 동전0

단계별로 풀어보기 그리디 알고리즘의 1단계 문제

11047번: 동전 0

이번학기 알고리즘 수업에서 그리디 알고리즘 단원에 들어갈 때 첫번째로 배운 예제여서 어떻게 푸는지는 당연히 알고 있었다.

동전의 가치가 높은 순으로 정렬하고 그 동전을 추가시켰을 때 원하는 금액이 넘지 않으면 추가시키고 아니면 그 다음 동전에서 그 과정을 반복한다.

from sys import stdin
n, k = list(map(int, stdin.readline().split()))
value = []
for i in range(n):
    value.append(int(input()))
total = 0
count = 0
while total != k:
    for j in range(n - 1, -1, -1):
        if total + value[j] <= k:
            total += value[j]
            count += 1
            break
print(count)

이렇게 제출했더니 시간초과가 났다. 무한루프에 빠진걸까?

 

혹시 몰라서 똑같은 코드를 언어만 자바로 바꿔서 이렇게 제출했더니

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int k = in.nextInt();
        int[] value = new int[n];
        for (int i = 0; i < n; i++) {
            value[i] = in.nextInt();
        }
        int remain = k;
        int count = 0;
        int start = n - 1;
        while (remain != 0) {
            for (int j = start; j >= 0; j--) {
                if(remain >= value[j]) {
                    int temp = remain / value[j];
                    remain = remain % value[j];
                    count += temp;
                    start = j;
                    break;
                }
            }
        }
        System.out.println(count);
    }
}

성공이었다.

이유를 모르겠다. 자바가 파이썬보다 빠른가? 흠

 

파이썬 코드를 조금 개선해서 이렇게 제출했더니

from sys import stdin
n, k = list(map(int, stdin.readline().split()))
value = []
for i in range(n):
    value.append(int(input()))
remain = k
count = 0
start = n - 1
while remain != 0:
    for j in range(start, -1, -1):
        if remain >= value[j]:
            temp, remain = divmod(remain, value[j])
            count += temp
            start = j
            break
print(count)

60ms로 성공이었다.

 

정말로 자바가 파이썬보다 빠른가 싶어서 이 똑같은 코드를 자바로 이렇게 제출해보았다.

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int k = in.nextInt();
        int[] value = new int[n];
        for (int i = 0; i < n; i++) {
            value[i] = in.nextInt();
        }
        int remain = k;
        int count = 0;
        int start = n - 1;
        while (remain != 0) {
            for (int j = start; j >= 0; j--) {
                if(remain >= value[j]) {
                    int temp = remain / value[j];
                    remain = remain % value[j];
                    count += temp;
                    start = j;
                    break;
                }
            }
        }
        System.out.println(count);
    }
}

성공이긴 한데 파이썬보다는 느린 104ms로 성공이었다.

정말 뭐지? 첫번째 코드는 왜 시간초과가 난걸까