<이것이 취업을 위한 코딩 테스트다>를 공부하고 정리한 내용입니다.
문제
어떠한 수 N이 1이 될 때까지 다음의 두 과정 중 하나를 반복적으로 선택하여 수행하려고 한다. 단, 두 번째 연산은 N이 K로 나누어떨어질 때만 선택할 수 있다.
1. N에서 1을 뺀다.
2. 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번의 과정을 수행해야 하는 횟수의 최솟값을 출력한다.
입력 예시
25 5
출력 예시
2
해설
-
나의 코드
- 그냥 1이 될 때까지 수행해주는 정직한 코드
- 🍀아무래도 나누는 것이 n이 빨리 작아지니 나누는 수행에 우선순위 두기
- 그러나 시간 복잡도는 수행횟수만큼 딱 나오는 정직한 비효율적 코드
n, k=map(int, input().split()) #n과 k 입력받기 cnt=0 #수행 횟수 세기 while n>1: #n이 1이 되기 전까지 수행 if n%k==0: #나누어지면 n/=k #나눠줘라 else: #아니라면 n-=1 #빼줘라 cnt+=1 #수행 횟수 +1 print(cnt) #최소 횟수 출력 -
단순한 답안 예시
- 🍀n의 범위를 k를 기준으로 나누어떨어질 수 있는 희망편(k랑 같거나 큼)/ 절망편으로 (k보다 작음)으로 나눔.
- 🍀나누어 떨어질 수 있는지를 확인하고, 그렇지 않다면 나누어떨어지게 먼저 만듦.
- 빼기 먼저, 나누는거 나중
- 뺄 때, 한번에 빼니까 그만큼 반복 횟수 줄여줌(?)
- 그러나 이중 반복 사용
n, k=map(int, input().split()) #n과 k 입력받기 cnt=0 #수행 횟수 세기 while n>=k: #n이 k보다 크거나 같을 동안 while n%k!=0: #나누어 떨어지지 않을 동안 n-=1 #1씩 빼주는 연산 수행 반복 cnt+=1 #횟수도 잊지 않고 세주기 n//=k #나누어 떨어지면 몫을 n에 저장 cnt+=1 #횟수 누적 while n>1: #n이 k보다 작고 1보다 클동안 n-=1 #1씩 빼주는 연산 수행 반복 cnt+=1 print(cnt) #최소 횟수 출력 -
보다 효율적 답안 예시
- 2번이랑 같은 알고리즘 흐름. - k보다 같.큼 / 작을때
- 빼기 먼저, 나누는거 나중
- 🍀나누어 떨어질 수 있는지를 확인하지 않고, 타겟을 설정해 나누어 떨어지게 먼저 만듦.
- 🍀뺄 때 한번에 빼니까 그만큼 반복 횟수 줄여줌.
n, k=map(int, input().split()) #입력 cnt=0 #수행 횟수 세기 while True: target=(n//k)*k #n이 k로 나누어떨어질 가장 가까운 수 cnt+=(n-target) #그 수가 될때까지 1씩 빼줄테니까 그만큼을 수행 횟수로 추가 n=target #그러면 k로 나누어떨어질 수가 되어있을것. if n<k: #n이 k보다 작으면 탈출 break n//=k #n이 나누어 떨어질 타이밍이니 몫을 n에 저장 cnt+=1 #횟수 누적 cnt+=(n-1) #n이 k보다 작을때 1이 될때까지 빼줄테니까 그만큼을 수행 횟수로 추가 print(cnt)
매일매일이 새로운 시작점