Search

1이 될 때까지

문제 : 1이 될 때 까지

어떠한 수 N이 1이 될 때까지 다음의 두 과정 중 하나를 반복적으로 선택하여 수행하려고 한다. 단, 두 번째 연산은 N이 K로 나누어 떨어질 때만 선택할 수 있다. 1. N에서 1을 뺀다. 2. N을 K로 나눈다. 예를 들어 N이 17, K가 4라고 가정하자. 이때 1번의 과정을 한 번 수행하면 N은 16이 된다. 이후에 2번의 과정을 두 번 수행하면 N은 1이 된다. ( 16/4 = 4 -> 4/4 = 1 ) 결과적으로 이 경우 전체 과정을 실행한 횟수는 3이된다. (1번은 1을 뻔것 2번과 세번은 k로 나눈 것) 이는 N을 1로 만드는 최소 횟수이다.

문제

N과 K가 주어질 때 N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야 하는 최소 횟수를 구하는 프로그램을 작성하시오.

입력 조건

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

출력 조건

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

입력 예시

25 5
Python

출력 예시

2
Python

단순하게 푸는 답안

n, k = map(int, input().split()) result = 0 # N이 K 이상이라면 K로 계속 나누기 while n >= k: #N이 K로 나누어지지 않는다면 N에서 1씩 빼기 while n % k != 0: n -= 1 result += 1 # K로 나누기 n //= k result += 1 # 마지막으로 남은 수에 대하여 1씩 빼기 while n > 1: n -= 1 result += 1 print(result) # 최종 답안 출력
Python

위 방식의 문제점? : M이 100억 이상처럼 크기가 크면 시간 초과 판정!

모범 답안

해결에 필요한 핵심 아이디어: 최대한 많이 나누자!

해결 시나리오

1.
필요한 변수
나눠지는 수(n) / 나누는 수(k) / 연산 횟수(result) / k와 나누어 떨어지는 수(target)
2.
N이 K로 나눠지는 수가 될 때까지 1씩 뺀다.
result += (n - target)
n = target
3.
더 이상 나눌 수 없을 땐 반복문 탈출
4.
n을 k로 나누기
답안

나동빈님 컨텐츠를 이용하시면 더 많고 자세한 내용을 얻을 수 있습니다.