본 포스팅은 해당 문제에 대한 정답(그리디 이용 풀이)과 문제 상황을 해결할 수는 있지만 시간초과가 나는 풀이(브루트포스 풀이) 두 가지를 제시한다.
후자는 구현 연습용이므로 정답을 원하는 분은 '✏️ 풀이 1'만 참고하기를 바란다.
📄 문제
백준
난이도 : Silver 4
문제 제목 : 동전 0
✏️ 풀이 1
import sys
input = sys.stdin.readline
n, k = map(int, input().split())
kind = [int(input()) for _ in range(n)]
result = 0
for i in range(n - 1, -1, -1):
result += k // kind[i]
k %= kind[i]
print(result)그리디로 풀 수 있는 문제이다. 주어지는 동전의 가치는 항상 다른 동전의 배수이기때문에 그리디로 풀 수 있는 것이다. (그렇지 않으면 아마 DP나 백트래킹(브루트포스) 등으로 풀어야 할 것이다.)
동전의 개수를 최소화하려면 가장 큰 동전을 최대한 많이 써야 하는 것에 집중해야 한다.
✏️ 풀이 2 / 오답(시간초과)
import sys
input = sys.stdin.readline
n, k = map(int, input().split())
kind = [int(input()) for _ in range(n)]
end = 0
for i in range(n):
if k < kind[i]:
end = i - 1
break
num = [0] * n
def get_result(num, total, goal, n):
if total == goal:
print(sum(num))
sys.exit(0)
for i in range(n, -1, -1):
while goal - total >= kind[i]:
num[i] += 1
total += kind[i]
get_result(num, total, goal, n - 1)
while num[i]:
num[i] -= 1
total -= kind[i]
get_result(num, total, goal, n - 1)
get_result(num, 0, k, end)가능한 모든 동전 조합을 확인해보는 풀이로, 브루트포스 풀이이다.
- 우선 목표 값(
k)보다 크지 않은 동전 종류로 범위를 좁힌다. - 그리고 동전의 종류별로 사용한 수를 카운팅하는 배열(
num)을 둔다. - 큰 동전부터 목표 값을 넘지 않을 때까지 해당 동전 사용 개수를 증가시키고, 그 동전보다 한 단계 작은 동전으로 같은 동작을 하는 것을 반복한다.(재귀)
그리고 가장 큰 동전을 목표 값에 가장 가깝도록 최대한 사용하는게 답이 아닐 수 있으니,num[i] -= 1을 하며 재귀를 한번씩 해준다.
예를 들어 100원, 500원 동전으로 1100원 만들기 일때,
500원을 최대한으로 사용한 후(2개), 100원을 최대한으로 사용할 (1개) 경우가 있다.
그러나 500원을 1개만 사용한 후, 100원을 1100원을 초과하지 않는 최대한으로 사용할 경우도 있으므로 그것을 다 확인해보는 것이다.
✅ 이 풀이는 모든 가능한 조합을 확인하기에 괜찮은 방법이다.
이 문제의 답을 찾기에는 비효율적이나 말 그대로 '가능한 모든 동전 조합 찾기'나 '동전이 다른 동전의 배수가 아닐 때'를 고려해서 연습삼아 구현해본 풀이이다.
📦 GitHub
해당 문제, 풀이에 대한 GitHub Repository 링크는 다음과 같다.
GitHub - 백준(Silver) '11047. 동전 0'
GitHub - [17강] 그리디/연습문제 '11047. 동전 0'
사실 문제를 읽고 그리디 문제같다는 생각은 들었지만,
'만약 동전이 다른 동전의 배수가 아니면 어떻게 풀지?'라는 생각에 더 꽂혀서 그 상황에 대해 더 공부를 해본것 같다.
'✏️ 풀이 2'도 그래서 나온 풀이이다. 그러나 해당 풀이의 경우 시간초과가 날 확률이 높은 것 같아 DP 등 다른 방법의 풀이를 더 고민해봐야겠다.
