1이 될 때까지

 

문제

N이 1이될 때까지 1을빼거나 K로 나눈다. 이 때, 최소한의 연산으로 1을 만들어라.

 

유형파악

다른 알고리즘 연결이 안된다.

그리디 알고리즘이다.

 

아이디어

직관적으로 최대한 K로 나누는게 숫자 1을 만드는데 더 빨리 가까워진다.

나누어 떨어지면 K로 나누고 아니면 1을 뺸다.

 

정당성

직관적으로 나누는게 항상 1을 빼는거 보단 숫자가 더 빨리 작아지므로 정당하다고 볼 수 있다.

 

구현

- K로 나눠지는지 확인

- 나눠지면 K로 나눈다. 아니면 1을 뺀다

- 1이 될때까지 반복한다.

 

코드

n = int(input("입력 : "))
k = int(input("입력 : "))

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

 

 

공간 체크

- 저장하는 것이 n, k, count 정도 인데, 12바이트이므로 딱히 고려할 필요는 없다/

 

 

시간 체크

- 이 문제의 시간 제한은 1초이다. 파이썬은 평균적으로 1초에 5000만번정도의 연산이 가능하다.

최악의 경우 N=100000, K=2인데 21번의 연산으로 1을 만들 수 있다.

따라서, 충분하다