그리디 - 1이 될 때까지(Swift)

본 내용은 '이것이 취업을 위한 코딩테스트다 with 파이썬' 책을 기반으로 포스팅 하였습니다.

 

문제

저작권 문제가 될 수 있어 문제는 삭제합니다.

 

풀이코드

입력	출력
25 5	2

var n = 25
let k = 5
var count = 0

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

print(count) // 2

 

문제 풀이

1. n이 k의 배수가 될때까지 1씩 빼주면서 1씩 카운트 증가

2. n이 k의 배수라면 n을 k로 나눈 몫을 n에 넣어주고 카운트 증가 

3. 위 과정을 반복하면서 n이 1이 되었을때 break로 while문 탈출 

※ 여기서 n을 k로 최대한 많이 나누는것이 반복횟수를 줄일수 있는 방법이다.