P11047. 동전 0

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

11047번: 동전 0

설명

K원을 만드는데 필요한 동전 개수의 최솟값을 구하기 위해 K원보다 작은 수 중 가장 인접한 수부터 하나씩 빼기 시작했다.

 

이진 탐색

본인은 인접한 수를 찾을 때, 이진 탐색을 사용했는데 값을 업데이트할 때마다 K원보다 작은 수 중 가장 인접한 수를 찾고 빼는 방식을 사용한다면, 시간 초과가 발생한다.

 

이를 해결하기 위한 방법은 간단하다. 한번에 인접한 수 하나를 빼지 않고, 뺄 수 있을만큼 빼는 것이다. 

이것은 K를 가장 인접한 수로 나누었을 때 몫이 동전의 개수가 되고, 나머지가 이후에 계산할 K의 값이 되는 것이다. 

 

즉 예시처럼 4200보다 작지만 가장 인접한 수는 1000일 때, 

4200 // 1000 = 4 ➡️ 동전 개수

4200 % 1000 = 200 ➡️ 이후에 계산할 K의 값

이 되는 것이다. 

div = findNearest(k)
count += k // div
k = int(k % div)

그리디

그리디 방식도 특별한 점이 있지 않다.

동전이 정렬되어 있기 때문에 맨 뒤에서부터 줄일 수 있을만큼 K의 값을 줄여나가는 것이다.

코드

이진 탐색

from sys import stdin as s
import sys

n, k = map(int, s.readline().split())
coin = []

for i in range(n):
    coin.append(int(s.readline()))

count = 0

def findNearest(k):
    left = 0
    right = len(coin) - 1

    while left <= right:
        middle = (left + right) // 2

        if k == coin[middle]:
            return coin[middle]
        elif k < coin[middle]:
            right = middle - 1
        elif k > coin[middle]:
            left = middle + 1

    if right <= -1:
        return coin[0]
    elif left >= len(coin):
        return coin[len(coin) - 1]
    else:
        return coin[right]

while k != 0:
    div = findNearest(k)
    count += k // div
    k = int(k % div)

print(count)

그리디

from sys import stdin as s
import sys

n, k = map(int, s.readline().split())
coin = []

for i in range(n):
    coin.append(int(s.readline()))

ans = 0
count = 0
a = len(coin) - 1
while k != 0:
    for i in range(a, -1, -1):
        if k - coin[i] >= 0:
            count += k // coin[i]
            k = int(k % coin[i])

print(count)

 

그리디 문제는 수학적으로 효율적인 방법을 찾는데 고민하는 시간이 필요한 것 같다. 다양한 문제를 풀이하며 실력을 항상시켜야겠다.