[Python] 백준 11047번. 동전 0

https://www.acmicpc.net/problem/11047

11047번: 동전 0

 

문제:

최소 동전의 갯수를 찾는 문제이다.

4200원이 주어졌을때 1000 * 4 와 100 *2 동전 6개로 최솟값을 찾을 수 있다.

 

풀이 설계

• p는 인덱스로 사용한다.
• k가 nlist[p] 보다 작으면 동전의 값이 더 크기 때문에 인덱스 값을 증가시켜준다.
  • ex) 4200 < 5000
• k가 nlist[p]보다 크면 
  • cnt = k // nlist[p] 예시로 1000 위치까지 가면 4200 // 1000 => 4개를 구할 수 있다.
  • k 는 k % nlist[p] 나머지를 저장해준다.

import sys

input = sys.stdin.readline
n, k = map(int, input().split())
nlist=[int(input()) for i in range(n)]
p=0
cnt=0

while k != 0:
	# k가 nlist[p] 보다 작으면 동전의 값이 더 크기 때문에 인덱스 값을 증가시켜준다
    if k > nlist[p]:
        p += 1
    # k가 nlist[p]보다 크면
    elif k <= nlist[p]:
        p -= 1
        cnt += k // nlist[p]
        # k 는 k % nlist[p] 나머지를 저장
        k -= k % nlist[p]
        p = 0

print(cnt)

 

풀이제출결과 틀렸습니다가 나왔다.

 

코드를 보니

• list를 역순으로 정렬하면 더 빨리 찾을 수 있다
• for문을 사용하여 값을 꺼내면 인덱스를 사용할 필요가 없다.

import sys

input = sys.stdin.readline
n, k = map(int, input().split())
nlist=[int(input()) for i in range(n)]
# list를 역순으로 정렬하면 더 빨리 찾을 수 있다
nlist.sort(reverse=True)
cnt=0

for num in nlist:
    if k < num:
        continue
    cnt += k // num
    k = k % num

    if k == 0:
        break

print(cnt)