[07.15] 백준 11047 - 동전 0 (파이썬)

그리디 알고리즘에 기초 of 기초 문제이다.

동전의 가치가 오름차순으로 주어지기 때문에 가장 큰 값부터 차례대로 내려오면서 계산하면 된다.

 

하지만 처음 시도했을 때는 시간 초과를 발생시켰다.

#백준 11047 동전 0 - 그리디 알고리즘
tn, tk = input('').split()
n = int(tn)
k = int(tk)
coin = []
cnt = 0

for i in range(n):
    coin.append(int(input('')))

for i in range(len(coin) - 1, -1, -1):
    if(coin[i] <= k):
        while coin[i] <= k:
            k -= coin[i]
            cnt += 1
    if(k == 0):
        break

print(cnt)

for문의 if문 안의 while문 때문에 시간초과가 발생한 것 같다. 이중for문을 돌리는 것과 같은 시간이 O(n^2) 시간이 소요되었을 것이다.

 

 

최종 코드는 이것이다.

 

11047.py

tn, tk = input('').split()
n = int(tn)
k = int(tk)
coin = []
cnt = 0
for i in range(n):
    coin.append(int(input('')))

for i in range(len(coin) - 1, -1, -1):
    if(coin[i] <= k):
        cnt += k // coin[i]
        k = k % coin[i]
    if(k == 0):
        break
print(cnt)

range쓰는 습관 기르기

소숫점 없애고 싶을 때는 // 연산자 사용하기

---

파이썬에서 한 줄에 여러개의 값을 받기 위해서는 다음과 같이 받아야 한다.

예를 들어 15, 20을 받는다고 치면

n, k = input('').split()

split() 함수에 인자를 안넣으면 공백으로 처리한다.

다만 n, k는 여기서 문자열이므로 따로 int로 바꾸어주어야한다.