[백준]11047_동전0

문항 분석

입력 제한

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000)

(1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)

가치가 더 큰 동전으로 가치가 더 작은 동전보다 더 적은 수를 활용해 합을 만들 수 있다.

가치가 큰 동전을 매번 하나씩 반복문을 통해 뺴는 방법을 사용하면 그만큼 시간적 소요가 크므로
나누기 연산과 나머지 연산을 활용해 접근하면 될 것 같다.

Code

import Foundation

let input = readLine()!.split(separator: " ").map{ Int(String($0)) }
var coins = [Int]()

let n = input[0]!
var k = input[1]!

var total = 0
(0..<n).forEach { _ in
    coins.append(Int(readLine()!)!)
}

for coin in coins.reversed() {
    if k == 0 {
        break
    }
    total += k/coin
    k %= coin
}
print(total)

결과 및 분석

• 입력 코드에서 map{Int(String($0))} 을 활용하는 방법을 사용함.

swift 제공 메서드 시간 복잡도
reverse() -> O(N)
reversed() -> O(1)