백준 (Baekjoon Online Judge) 그리디 - 11047번 동전

아이디어 1: 입력받은 큰 돈부터 빼봐야겠다!

#시간초과 코드 ㅜㅜ
a = list(map(int,input().split())) #
coin = []
sum = 0
for i in range(a[0]):
  money = int(input())
  coin.append(money)
coin.reverse()
for i in coin:
  while a[1]>=i: #입력받은 b원이 i보다 크면?
    a[1]=a[1]-i
    sum+=1

print(sum)

단순하게 가장 큰 돈의 단위부터 계속해서 빼고, 한번 빠질 때마다 sum에 1씩 더하려고 했는데, while 반복문을 돌면서 굉장히 시간적으로 효율이 떨어지는 것을 알 수 있다. 따라서 이런 문제에서 잘 사용할 수 있는 몫을 이용한 방법으로 코드를 다시 구현했다.

#성공!
a = list(map(int,input().split()))
coin = []
sum = 0
for i in range(a[0]):
  money = int(input())
  coin.append(money)

n = len(str(a[1])) #일단 자릿수를 구한다.
coin.reverse() #큰순서대로 정렬하고
for i in coin: #리스트를 한번씩 도는데
  if i<=a[1]: #만약 가장 큰 입력이 K원보다 작거나 같으면?
    sum = sum+ a[1]//i #K원을 코인으로 나눈 몫 만큼 sum에 더해주고
    a[1] = a[1] - i*(a[1]//i) #K원에서 코인만큼 빼준다.

print(sum)

이번 코드는 입력받은 K원이 몇자리 숫자인지 구한 후, 입력받은 원단위를 큰 순서대로 정렬 후 이를 이용해 

for문을 돌고 있는 원단위가 입력받은 K원보다 작다면 K원을 단위로 나눈 몫 만큼 sum에 더해주고 K원의 값을 업데이트 하는 방식으로 구현했다.

 

결과는 성공!

 

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