https://www.acmicpc.net/problem/11047
11047번: 동전 0
첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)
www.acmicpc.net
- 그냥 for문으로 loop를 순회하면 시간 초과가 발생한다.
- 따라서 몫을 구해 계산한다.
더보기
nk = list(map(int, str(input()).split()))
N = nk[0]
K = nk[1]
costList = []
for idx in range(N):
cost = int(input())
if(cost <= K):
costList.append(cost)
costList.sort(reverse=True)
answer = 0
costSum = K
costIdx = 0
while(True):
if(costSum == 0):
break
divValue = costSum // costList[costIdx]
if(0 < divValue):
answer += divValue
costSum -= (costList[costIdx] * divValue)
else:
costIdx += 1
print(answer)'Coding Problem > 백준' 카테고리의 다른 글
| [백준] 13305 - 주유소 (0) | 2021.05.28 |
|---|---|
| [백준] 1541 - 잃어버린 괄호 (0) | 2021.05.28 |
| [백준] 11399 - ATM (0) | 2021.05.28 |
| [백준] 2580 - 스도쿠 (0) | 2021.05.23 |
| [백준] 18870 - 좌표 압축 (0) | 2021.05.03 |