문제
준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.
동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000)
둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)
출력
첫째 줄에 K원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.
예제 입력
10 4200
1
5
10
50
100
500
1000
5000
10000
50000
예제 출력
6
나의 답안:
var coinArr = [Int]()
var num = readLine()!.components(separatedBy: " ").map{Int(String($0))!}
var k = num[1]
var count = 0
for i in 0..<num[0] {
var coin = Int(readLine()!)!
coinArr.append(coin)
}
for j in stride(from: num[0]-1, through: 0, by: -1) {
if k == 0 {
break
}
if k / coinArr[j] == 0 {
continue
} else if k / coinArr[j] != 0 && k/coinArr[j] > 0 {
count += k/coinArr[j]
k = k % coinArr[j]
}
}
print(count)
문제 설명:
가치의 합을 큰 동전에서 작은 순으로 나누어 간다. (탐욕 알고리즘 사용)
예로 5 , 4720을 입력한 후, 가지고 있는 동전을 10 100 1000 10000 50000 이라고 가정한다.
1. 4720을 가장 큰 동전인 50000으로 나눈다. 나눠지지 않으므로 나눈값은 0이다.
2. 4720을 다음으로 큰 동전인 10000으로 나눈다. 마찬가지로 나눠지지 않으므로 나눈값은 0이다.
3. 4720을 다음으로 큰 동전인 1000으로 나눈다. 4720/1000 = 4이므로 count가 4가된다. 가치의 합은 4720을 1000으로 나눈 나머지인 720이 된다.
4. 720을 다음으로 큰 동전인 100으로 나눈다. 720/100 = 7 이므로 count는 4+7인 11이 된다. 가치의 합은 720을 100으로 나눈 나머지 값인 20이 된다.
5. 20을 다음으로 큰 동전인 10으로 나눈다. 20/10 = 2 이므로 count는 11+2인 13이 된다. 가치의 합은 0이 된다.
6. 반복문이 종료되고 count 값인 13이 출력된다.
'코딩 테스트' 카테고리의 다른 글
행렬의 곱셉 구하기 문제 - swift (0) | 2022.11.07 |
---|---|
코딩 테스트 - [백준 1931] 회의실 배정(탐욕 알고리즘) (0) | 2022.09.20 |
코딩테스트 - Swift Array, Set, Dictionary 관련 함수 시간 복잡도 (0) | 2022.09.14 |
코딩테스트 - [백준: 10815] 숫자 카드(이진 탐색) (0) | 2022.09.14 |
코딩 테스트 - [백준 7568] : 덩치 (0) | 2022.09.14 |