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

1이 될 때 까지

어떠한 수 N,K가 입력이 들어오면 두가지의 연산을 통해 N의 값을 1로 만드는 과정 중 연산의 최소 횟수를 구하는 문제.

단, 두번째 연산은 N이 K로 나누어 떨어 질때만 선택할 수 있다.

 

1. N에서 1을 뺀다.

2. N을 K 로 나눈다.

 

 

나의 코드

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

cnt =0
while n!=1:
    if n%k==0:
        n=n//k
        cnt+=1
    else:
        n=n-1
        cnt+=1
print(cnt)

'최소 회수' 라는 단어에서 그리디 알고리즘을 떠올렸다.

또한 두가지 연상 종류 중 뺴기 보단 나누기가 횟수를 줄이는데 효과가 좋다.

 

우선 2번 연산이 가능한지(n이k로 나누어 지는지) 확인 후 가능하면 2번을 하고 2번 연산이 안되면 1번 연산을 한다.

 

정답 코드

# N, K공백을 기준으로 구분하여 입력 받기
n, k = map(int, input().split())

result = 0

while True:
    # N이 K로 나누어 떨어지는 수가 될 때까지만 1씩 빼기
    target = (n // k) * k
    result += (n - target)
    n = target
    # N이 K보다 작을 때 (더 이상 나눌 수 없을 때) 반복문 탈출
    if n < k:
        break
    # K로 나누기
    result += 1
    n //= k

# 마지막으로 남은 수에 대하여 1씩 빼기
result += (n - 1)
print(result)

음.. 정답 코드와 해설을 보았는데 그리디 알고리즘이라고 판단한 정당성과 풀이는 같지만

왜 이렇게 정답 코드의 코드가 부산 스럽고 굳이 필요 없는 코드들이 많다고 느껴지는거지.....

나의 코드가 일반적으로 주어진 단 하나의 입력 값에만 되고 시간 초과가 잘 나는 코드인건가..?

아닌거 같은디 흠..

 

우선 지금은 내가 쓴 코드가 더 나은듯 ㅇㅅㅇ