[그리디] 1이 될 때까지 - swift

코드는 Swift로 작성하였습니다.
제가 직접 작성한 코드라 최적의 코드가 아닐 수 있음을 알려드립니다. 🐹

문제는 저작권 관련 문제가 있을 수 있어서 적어두지 않았습니다.

✍🏻 생각정리

내가 처음 생각했던 알고리즘

1. k로 나누어 떨어지면 나누고 아니면 뺀다
2. 그 과정을 반복한다.
   

why?
1에 가까워지는 속도는 나누기가 빠름.
나눌 수 있을 때 나누는 것이 가장 좋은 방법이라고 생각했다.

=> 정답 !!!

👩🏻‍💻 코드

import Foundation

let intArr = readLine()!.split(separator: " ").map{Int($0)!}
var n = intArr[0]
let k = intArr[1]
var count: Int = 0

while(n != 1) {
    if n % k == 0 {
        n /= k
    }
    else {
        n -= 1
    }
    count += 1
}


print(count)

이건 내가 가장 처음 적었던 코드

let intArr = readLine()!.split(separator: " ").map{Int($0)!}
var n = intArr[0]
let k = intArr[1]
var count: Int = 0

while true {
    // target : k로 나누어 떨어지는 수
    // target을 구한 후 그 때까지 빼준다.
    let target = (n / k) * k
    count += (n - target)
    n = target

    // 더 이상 안나누어지면 반복문 탈출
    if n < k {
        break
    }
    // k로 나누기
    count += 1
    n /= k
}
count += (n - 1)

print (count)

이건 동빈님 풀이 참고
위의 방식보다 시간이 적게 걸린다.

📚 참고자료

• 이것이 코딩테스트다