[Python] 1이 될 때까지(그리디)

문제

• 어떠한 수 N이 1이 될 때 까지 다음의 두 과정 중 하나를 반복적으로 선택하여 수행한다
• 단 두 번째 연산은 N이 K로 나누어 떨어질 때만 선택할 수 있다.

입력

• 첫째 줄에 N (2 <= N <= 100,000)과 K (2 <= K <= 100,000)가 공백으로 구분되어 주어진다
• 입력으로 주어지는 N은 항상 K보다 크거나 같다

출력

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

문제 풀이 1 

• N이 1보다 클 때 N이 K로 나누어 떨어지지 않는 경우 계속 1을 뺀 후, 연산 횟수를 카운트 한다
• N이 1보다 클 때 N이 K로 나누어떨어지는 경우 N을 K로 나누고, 연산 횟수를 카운트 한다
• 연산 도중 N이 1이 된다면 while문을 빠져나온다
• 연산 횟수를 출력한다

코드

n, k = map(int,input().split())
cnt = 0
while n > 1:
    if n == 1:
        break
    if n % k == 0 :
        n //= k
        cnt += 1
    if n == 1:
        break
    if n % k >= 1:
        n -= 1
        cnt += 1

print(cnt)

문제 풀이 2

• N의 값이 K이상인 경우 가장 많이 나누는 방법을 선택
• N의 값이 K이상일 때 N이 K로 나누어 떨어지지 않는다면 나누어 떨어질 때 까지 1을 빼고 연산 횟수 카운트
• K로 나누어 떨어지는 수가 되면 K로 나눈 후, 연산 횟수 카운트
• N이 1보다 크고, K미만인 경우 1을 계속 뺀 후 연산 횟수를 카운트
• 연산 횟수 출력

코드

n, k = map(int,input().split())
cnt = 0
while n >= k:
    while n % k != 0:
        n -= 1
        cnt += 1
    n //= k
    cnt += 1

while n > 1:
    n -= 1
    cnt += 1
print(cnt)

문제풀이 3

• N을 K로 나누어 떨어지는 값으로 만들기
• n - target 값 만큼 연산 횟수를 카운트
• N이 K보다 작은 경우 나눌 수 없는 경우이므로 while문 탈출
• N을 K로 나누고 연산 횟수 카운트
• N이 K보다 작아 반복문 탈출한 경우 N - 1 값을 연산횟수에 더하기
• 연산횟수 출력

코드

n, k = map(int,input().split())
cnt = 0
while True:
    # N을 K로 나누어 떨어지는 값 만들기
    target = (n // k) * k
    cnt += (n - target)
    n = target
    # K보다 작을 때 반복문 탈출
    if n < k:
        break
    # K로 나누기
    n //= k
    cnt += 1

cnt += (n - 1)
print(cnt)