<aside> 💡 그리디란!
이 문제를 보면, ‘최소 동전갯수’로 거스름돈을 주어야합니다. 그렇게 하기 위해서 가장 좋은 방식은? ‘가장 큰 돈을 우선적으로 주는 것’이 가장 좋겠죠. 즉, 500원 짜리부터 아주 탐욕적으로 줘버린다는 소리가 바로 그리디입니다. (나머지 동전들은 고려하지 않은채 500원짜리 먼저 거슬러준다는 것! 500원짜리 이놈이 아주 욕심쟁이다~ 본인이 먼저 거슬러지려고한다~ 이렇게 생각했어요 전..)
let wallet = [500, 100, 50, 10, 5, 1]
func giveChange(_ wallet: [Int]) -> Int {
var result = 0
var change = 1000 - Int(readLine()!)!
for coin in wallet {
let coinCount = change / coin
result += coinCount
change -= coin * coinCount
}
return result
}
print(giveChange(wallet))
import Foundation
var nmk = readLine()!.split(separator: " ").map { Int($0)! }
var n = nmk[0]
var m = nmk[1]
var k = nmk[2]
var arr = readLine()!.split(separator: " ").map { Int($0)! }
var count = 0
var result = 0
arr.sort(by: >)
while true {
if m == 0 { break }
if count == k {
result += arr[1]
count = 0
m -= 1
} else {
result += arr[0]
count += 1
m -= 1
}
}
print(result)
<aside> ⚠️ 하지만 이렇게 했을 때, M의 범위가 100억 이상이 된다면 어떻게될까?
시간초과가 날 것이다. → 해결 방식을 생각해보자.
</aside>
규칙을 찾아보자.
수열을 바라보면서 수학적으로생각 하여 식을 간단하게 만들어줄 필요가 있다. (최대한 반복 연산을 줄여야 시간복잡도가 줄어들 것이다.)
가장 큰 수는 K번 반복해서 더할 수 있다. 우리는 최대값을 구해줄 예정이라, 가장 큰 수를 K번 더해주고, 그다음 큰 수를 1번 더해줄 것이다. → 즉, 우리 수열은 (K+1) 길이를 가진 덩어리가 반복된다.
총 수는 8번 더할 수 있다. 우리가 지금 구한 한 덩어리의 길이로 M을 나눠주면, 덩어리가 몇번 반복되는지 나온다. → M / (K+1)
우리는 위에서 ‘몇 덩어리가 등장하는지’ 구했다. 여기다가 다시 K를 곱해주면, 가장 큰 수가 등장하는 횟수가 될 것이다. → (M / (K+1)) * K
우리는 M/(K+1)의 나머지도 고려해주어야 한다. 나머지만큼 가장 큰수는 더 더해질 수 있다. → (M % (K+1)) 이만큼 K는 더 더해진다.
<aside> 🔢 그래서 가장 큰 수가 등장하는 횟수는
((M / (K+1)) * K) + (M % (K+1))
</aside>
두번째로 큰 수를 더해주는 횟수는 바로 구할 수 있다.