1이 될 때까지
- 시간 제한 : 1초
- 메모리 제한 : 128MB
- 기출 : 2018 E 기업 알고리즘 대회
문제
어떠한 수 N이 1이 될 때까지 다음의 두 과정 중 하나를 반복적으로 선택하여 수행하려고 한다. 단, 두 번째 연산은 N이 K로 나누어 떨어질 때만 선택할 수 있다.
- N에서 1을 뺀다.
- N을 K로 나눈다.
예를 들어 N이 17, K가 4라고 가정하자. 이때 1번의 과정을 한 번 수행하면 N은 16이 된다. 이후에 2번의 과정을 두 번 수행하면 N은 1이 된다. 결과적으로 이 경우 전체 과정을 실행한 횟수는 3이 된다. 이는 N을 1로 만드는 최소 횟수이다.
N과 K가 주어질 때 N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야 하는 최소 횟수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N(2 <= N <= 100,000)과 K(2 <= K <= 100,000)가 공백으로 구분되며 각각 자연수로 주어진다. 이때 입력으로 주어지는 N은 항상 K보다 크거나 같다.
출력
첫째 줄에 N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야 하는 횟수의 최솟값을 출력한다.
풀이
N이 K로 나누어 떨어지는 수가 나올 때까지 1을 빼준 횟수와 이후 K로 나눈 횟수를 더해 출력해주었다.
책에서도 비슷한 방식을 이용한 방식과 N이 100억 이상과 같은 큰 수가 되는 경우 가정했을 때 보다 빠르게 연산을 진행하기 위해 N이 K의 배수가 되도록 만들어서 횟수를 구할 수 있다는 것을 알게되었다. 이러한 방식을 이용한 코드 또한 작성해보았다.
나의 답안 1
N, K = map(int, input().split())
count = 0
while N != 1:
if (N % K != 0):
N -= 1
else:
N //= K
count += 1
print(count)
나의 답안 2
N, K = map(int, input().split())
count = 0
while True:
if (N % K != 0):
count += N % K
N -= N % K
else:
N //= K
count += 1
if N < K:
break
print(count)
Ghost