[파이썬] 백준 알고리즘 11047 : 동전 0, python

예시

10 4200
1
5
10
50
100
500
1000
5000
10000
50000

결과

6

---

문제 풀이

처음 시도한 방법은 주워진 동전의 큰 값부터 차례로 K(모든 동전의 합)과 비교함. 하지만 K의 범위가 1억 이므로 이 방법은 부적합 판단.

잘못된 풀이

N, K = map(int, input().split())
money = []
sumMoneyLi = []
sumMoney = 0
countNum = 0

for i in range(N):
    money.append(int(input()))

print(money)
# while 1:
#     if sumMoney == K:
#         print(countNum)
#         break

for i in range(len(money)):
    if money[i] > K:
        sumMoneyLi.append(money[i-1])
        for k in range(1, 11):
            if sumMoneyLi[0]*k > K:
                sumMoneyLi[0] = sumMoneyLi[0]*(k-1)
                break

        for j in range(i):
            if sumMoneyLi[0] + money[j] > K:
                sumMoneyLi.append(money[j-1])
                for l in range(1, 11):
                    if sumMoneyLi[0]+sumMoneyLi[1]*l > K:
                        sumMoneyLi[1] = sumMoneyLi[1]*(l-1)
                        break

        break

print(sumMoneyLi)

 

정답 코드

from audioop import reverse
# N: 동전의 종류, K: 동전의 합
N, K = map(int, input().split())
# 입력 값을 받는 곳
money = []
# 동전 개수 카운팅
sumMoney = 0

# 입력 값을 리스트에 넣음
for i in range(N):
    money.append(int(input()))

# 역순으로 치환
money.reverse()

# 높은 수 부터 나눈 몫을 카운트 함
for j in money:
    sumMoney += K//j
    # 나머지 반환
    K %= j

# 결과
print(sumMoney)

다른 방법으로 주어진 동전의 높은 번호부터 K값을 차례대로 나누었다. 그 뒤 "//"를 이용하여 몫 만을 따로 카운트하였다. 만약 K 값이 1500이라면, 5000으로 나누면 몫은 0으로 sumMoney에 0이 카운트되어 값이 증가하지 않는다. 하지만 K를 1000으로 나누면 몫은 1이므로 카운트가 1 증가한다.

그다음 K를 1000으로 나눈 나머지 값(%)을 반환한다.