백준 11047번 : 동전 0 - 파이썬 (python)

www.acmicpc.net/problem/11047

11047번: 동전 0

* 방법1

- 아이디어

(1) 입력받은 동전의 가치를 내림차순으로 정렬한다.

(2) 가치의 합 K 보다 작거나 같은 값의 인덱스를 찾는다.

(3) K를 coin[i] (가치의 합 K 보다 작거나 같은 값)으로 나눈 몫을 result에 더한다.

(4) K 값을 K - ((k // coin[i]) * coin[i]) 로 변경한다.

 

- 테스트케이스 1

10 4200

1

5

10

50

100

500

1000

5000

10000

50000

 

(1) 위의 경우 coin = [50000, 10000, 5000, 1000, 500, 100, 50, 10, 5, 1] 으로 정렬한다.

(2) 가치의 합 K (=4200) 보다 작거나 같은 값의 인덱스 (= 3 / coin[3] = 1000)

(3) result = result + (k // coin[3]) 이므로 result = 0 + (4600 // 1000) = 4

(4) k = 4600 - ((4600 // 1000) * 1000) = 600

→ for문 반복

 

# n: 동전의 종류
# k: 동전의 합
n, k = map(int, input().split())
coin = []
index = 0
result = 0

# 동전의 가치 입력 (오름차순)
for i in range(n):
    x = int(input())
    coin.append(x)

coin.sort(reverse=True)

for i in range(n):
    if coin[i] <= k:
        index = i
        result += k // coin[i]
        k = k - ((k // coin[i]) * coin[i])

print(result)

 

 

 

github.com/501501/baekjoon/blob/master/11047.py

501501/baekjoon