[Swift] 백준 11047 - 동전 0
Greedy 알고리즘
매 선택의 순간마다 당장 눈앞에 보이는 최적의 선택만을 하여 최종적인 답에 도달하는 알고리즘이다.
(이러한 선택의 결과가 항상 최적이라는 보장은 없지만 그리디 알고리즘을 적용하는 문제에서는 최적이 된다.)
예를 들면?
최소 값을 찾아야하는 트리 구조가 있다고 하자
3
4 2
1 6 5 10
트리가 다음과 같이 생겼을 때
그리디 알고리즘은 3 -> 2-> 5 를 거쳐 5를 최소 값으로 판별한다.
이 예제에서 실제 최소 값은 1이지만, 그리디 알고리즘에서는 당장 눈앞에서 최적의 선택을 한 그 결과가 항상 최적 값으로 보장되기 때문에 이러한 경우는 문제로 나오지 않는다.
백준 11047 - 동전 0
풀이
그리디 알고리즘을 사용하는 대표적인 문제이다.
만들어야하는 K원보다 값이 작은 동전 중에서 가장 큰 값을 고르면 되는 문제이다.
최종 코드
import Foundation
let line = readLine()!.split(separator: " ").map{Int(String($0))!}
let N = line[0]
var K = line[1]
var coinArr = Array(repeating: 1000000, count: 10)
for i in 0..<N {
let coinValue = Int(readLine()!)!
coinArr[i] = coinValue
}
var count = 0
for i in (0..<N).reversed() {
let nowCount = K / coinArr[i]
K -= nowCount * coinArr[i]
count += nowCount
if K == 0 {
break
}
}
print(count)
- 큰 값부터 찾아야하니 reversed()를 사용한다.
- coinArr[i] 값이 K보다 크더라도 nowCount값이 0이 되니 신경쓰지 않아도 된다.
Author And Source
이 문제에 관하여([Swift] 백준 11047 - 동전 0), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@sun02/Swift-백준-11047-동전-0저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)