[BOJ] 11047. 동전 0 (Python3)

 

www.acmicpc.net/problem/11047 (level: Silver II)

11047번: 동전 0

---

 

최근 그리디를 공부하고 있는데, 짝꿍이 가장 기본이 되는 문제를 보내줘서 풀어보았다.

 

내가 보고 있는 책에도 이 문제처럼 거스름돈 관련한 문제가 예제로 나와있었는데, 이런 거스름돈 문제가 꼭 그리디라는 것은 아니고 큰 단위가 항상 작은 단위의 배수일 때, 즉, 작은 단위의 동전들을 조합해 다른 해가 나올 수 없을 때 쉽게 생각할 수 있는 '그리디' 방법으로 문제를 풀 수가 있다.

 

그리고 이 백준 11047번 문제 역시 문제에 나와 있는 Ai는 Ai-1의 배수 (티스토리에서 아래첨자 어떻게 쓰는지 모르겠어서 그냥 씁니다,,^_^) 라는 조건에 의해 그리디라는 조건이 충족되는 것으로 판단된다.

 

---

 

민지's 풀이

이제 그리디로 풀면 된다는 것에 확신을 얻었으니, 방법을 생각해봤다.

 

이 문제는 입력을 작은 수부터 받게끔 되어있었는데 실제 로직을 수행할 때는 단위가 큰 것부터 비교해야하기 때문에 나는 입력 받을 때 아예 배열을 만들어놓고 그 배열의 맨 뒤부터 입력값을 저장하도록 했다. 그러면 입력을 다 받은 후에 sort를 따로 해줘야하는 번거로움이 사라지니까!

 

결과적으로는 배열에 작은 단위의 동전 가치부터 저장되어 있을테니 실제로 비교하는 로직을 수행할 때는 배열의 맨 앞에서부터 비교해나가면 되는 것이다.

 

민지's 풀이

그리고 핵심이 되는 로직은 K를 어떻게 업데이트 해줄 것인가?였다. 즉, 그 방식의 문제.

내가 생각해낼 수 있었던 방식은 크게 빼기 연산과 몫을 구해서 활용하는 연산 두 가지였다.

 

1. K(가치의 합)과 현재 동전 가치를 비교하면서 K에서 동전의 가치만큼 빼주는 과정을 반복한다. (0 이상인 동안) 이 과정을 한 번 수행할 때마다 동전의 개수도 1씩 증가시킨다.

2. K(가치의 합)을 현재 동전 가치로 나누기 연산한 후, 몫을 구해 그만큼 동전 개수를 증가시킨다. K의 값은 현재 동전 가치에 방금 구한 몫을 곱한 만큼 뺌으로써 update 해준다.

 

---

 

결과부터 이야기하자면, 처음에는 1번째 방법(0 이상인 동안 계속 빼기 연산 반복)으로 구현했었는데 답안 제출 후 70~71%쯤 되었을 때 시간초과가 났다. 사실 예상한 결과였어서 그리 놀랍진 않았다.😂

이후, 무난하게 나누기 연산을 때린 후 몫을 구해 해결하는 2번째 방법을 사용해 문제를 풀 수 있었다.

 

# date: 2021/04/22
# author: psS2mj
# brief: BOJ_11047_동전 0

N, K = map(int, input().split())
cnt = 0 # 필요한 동전의 최소 개수

# 동전의 가치를 배열 뒤에서부터 차례대로 저장
coins = [0]*N
for i in range(N):
    coins[N-1-i] = int(input())

idx = 0
while K > 0:
    cost = coins[idx]
    if K >= cost:
        div = K//cost
        cnt += div
        K -= cost*div
    idx += 1

print(cnt)

 

✅ 로직은 내가 위에서 말한 대로, 입력을 받을 때 배열의 맨 뒤부터 받고 실제 로직 수행 시에는 배열 맨 앞에서부터 (동전 단위가 가장 작은 것부터) 비교하도록 했다.

 

✅ 그리고 while문의 조건은 K > 0로 줘서, 반복 수행 시 K를 계속 업데이트 해주면서 그 값이 0 이상인 동안에는 계속 돌도록 했다. (아직 가치의 합을 달성하지 못한 경우!)

 

✅ 또 내 코드에서 나름 핵심인 부분은 while문 안에 있는 if문인데, 동전의 가치가 K보다 큰 경우에는 로직을 수행하지 않고 지나가도록 했다.

예를 들어, K=4200인데 현재 동전의 가치(cost)가 5000이라면 비교할 필요 자체가 없으니 그냥 넘기도록 했다고나 할까? 반대로 K=4200인데 현재 동전의 가치가 1000이라면 if K >= cost라는 조건에 부합하므로 그 안의 로직을 수행하게 될 것이다.

 

✅ 위 로직을 수행한 후에는 인덱스 값을 1 증가시켜서 다음 반복 시 현재 동전의 가치보다 한 단계 작은 가치의 동전과 비교하도록 했다.

 

뿌-듯!

그리디 걸음마 성공!

 

나는 왠지 모르겠지만 그리디가 제일 부담스러운 느낌인데 이렇게 한 걸음씩 열심히 가봐야겠다^_^ ㅍㅇㅌ