[백준] 11047. 동전 0 - Python

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

11047번: 동전 0

---

• 생각1 - 이진 탐색
  • 뺄 수 있는 값 중 가장 큰 값을 이진 탐색을 통해 찾기
  • 그 값을  K에서 빼줄 수 있는 만큼 빼기
  • K가 0이 될 때까지 반복
• 코드1

from sys import stdin

input = stdin.readline

# 동전의 종류, 동전 가치의 합
N,K = map(int,input().split())
value = [int(input()) for _ in range(N)]

# 필요한 동전 개수의 최솟값
cnt = 0

# K보다 작은 값 중 가장 큰 값 찾기
def check(start,end):
    while start <= end:
        mid = (start + end)//2
        if value[mid] <= K:
            start = mid +1
        else:
            end = mid -1
    return end

while K > 0:
    # K보다 작은 값 중 가장 큰 값을 찾기
    coin = value[check(0,N-1)]
    
    # K가 coin보다 작아질 때까지 빼주기
    while K >= coin:
        K -= coin
        cnt += 1

print(cnt)

 

• 생각2 - for문
  • 큰 수부터 빼주기
    • K : 4200원
      • value[idx]가 5000원이면 빼줄 수 없다 -> value[idx] // 5000 == 0, value[idx] % 5000 == 4200
      • value[idx]가 1000원이면 4번 빼줄 수 있다. -> value[idx] // 1000 == 4,  value[idx] % 1000 == 200
• 코드2

from sys import stdin
input = stdin.readline

# 동전의 종류, 동전 가치의 합
N,K = map(int,input().split())
value = [int(input()) for _ in range(N)]

# 필요한 동전 개수의 최솟값
cnt = 0

# 큰 수 부터 빼주기
for idx in range(N-1,-1,-1):
    cnt += K // value[idx]
    K = K % value[idx]

print(cnt)