[Greedy] 1이 될때까지

이것이 코딩 테스트다 with Python
기출 : 2018 E 기업 알고리즘 대회
Greedy 알고리즘

문제

• 어떠한 수 N이 1이 될 때까지의 다음 두 과정을 반복적으로 선택하여 수행한다.
  • N에서 1을 뺀다.
  • N을 K로 나눈다.
• N이 K로 나누어 떨어질 경우 N을 K로 나누고 그렇지 않을 경우 N에서 1을 뺀다.

입력조건

• 첫째줄에 N(2 ≤ N ≤ 100,000) 과 K(2 ≤ K ≤ 100,000)가 공백으로 구분되며 각각 자연수로 주어진다. 이때 입력으로 주어지는 N은 K보다 항상 크거나 같다.

출력조건

• 첫째줄에 N이 1이 될때까지 1번 혹은 2번의 과정을 수행해야하는 횟수의 최솟값을 출력한다.

Solution

n, k = map(int, input().split())

count = 0

while True:
    if n == 1:
        break
    count += 1
    if n % k == 0:
        n = n / k
    else :
        n = n -1

print(count)

N과 K를 입력받고 N이 K로 나누어 떨어지면 N/K 그렇지않으면 N-1

• n, k = map(int, input().split()) : N과 K를 입력받음
• if n == 1: : N이 1이 됐으니 break
• count += 1 : N이 1이 아닌경우 연산 횟수를 count
• if n % k == 0: : N이 K로 나누어 떨어지는경우 N/K
• else : : 그렇지 않은경우 N-1