[swift] 백준 - 11047번: 동전 0

11047번: 동전 0

---

문제 푸는 데 있어 도움이 되도록 나의 풀이와 개선된 풀이를 올립니다.
또한 풀이 후 다른 사람의 풀이를 보고 참고할만한 풀이도 올립니다.
- 문제에 따라 나의 풀이만 있을 수 있습니다.
- 해당 풀이들은 풀이 중 하나일 뿐 최선의 풀이는 아닐 수 있습니다.

 

나의 풀이

let NK = readLine()!.split(separator: " ").map { Int($0)! }
let coin = (0..<NK[0]).map { _ in Int(readLine()!)! }.reversed()
var money = NK[1]
var count = 0
for i in coin {
    while money >= i {
        money = money - i
        count += 1
    }
}
print(count)

// 시간: 약 210ms

 

기본적인 그리디 알고리즘 문제네요.

큰 액수의 금액부터

가지고 있는 돈이 금액 보다 크다면

금액만큼 빼고 다시 반복하며

반복 횟수를 반환합니다.

 

하지만 시간복잡도가 맘에들지 않네요.

개선 방법이 있는지 찾아봐야겠습니다.

 

---

개선된 풀이

let NK = readLine()!.split(separator: " ").map { Int($0)! }
let coin = (0..<NK[0]).map { _ in Int(readLine()!)! }.reversed()
var money = NK[1]
var count = 0
for i in coin {
    count += money / i
    money %= i
    }
print(count)

 

시간을 많이 걸리게 한 범인은

for안에 있는 while문이었습니다.

 

풀이 방식을 바꿔

 

가지고 있는 돈(money)에서 금액이 나눠진다면

(가지고 있는 돈 / 동전의 금액)의 값을 count에 더해주고

 

나머지값은 그대로 money에 넣어

반복합니다.

 

사실 첫번째 풀이와 풀이 방식은 비슷하지만

사소한 부분에서

시간을 줄일 수 있는 방법을

공부해두면 좋을거 같습니다.

 

---