1이 될 때까지

출처:: 2018 E기업 알고리즘 대회

분류:: 그리디 

 

1. 문제 이해 및 해결과정

1. DFS 풀이 - DFS N-1로 연산 하는 경우 N/K로 연산하는 경우  로 두가지 가지 중 최소값을 생각했다  - 단 , 이 방법은 n이 100000이라면 overflow가 난다.  2. 그리디 풀이 - k로 최대한 많이 나누는 것이 최적의 해를 보장하는 것

 

2. 풀이방법

 1. DFS(n이 작을 때만 가능한 풀이)

#1이 될 때까지
#
import sys
sys.stdin = open("input.txt","r")
n,k=map(int,input().split())
sys.setrecursionlimit(10**6)
candi=[]
def DFS(x,cnt):
    if x==1:
        candi.append(cnt)
        return
    else:
        DFS(x-1,cnt+1)
        if x%k==0:
            DFS(x//k,cnt+1)
DFS(n,0)
print(min(candi))

 

 2. 그리디- 단순 풀이

#1이 될 때까지
#
import sys
sys.stdin = open("input.txt","r")
n,k=map(int,input().split())
cnt=0
while n>=k: #n보다 k가 같거나 크면 계속 나누기
    while n%k!=0:
        n-=1
        cnt+=1
    n//=k
    cnt+=1
while n>1: #나눌 수 없지만 뺄 수 있는 경우 ex)n=25 k=3일때 n=2가 되는 경우
    n-=1
    cnt+=1
print(cnt)

 

 3. 그리디 ★★

#1이 될 때까지
#
import sys
sys.stdin = open("input.txt","r")
n,k=map(int,input().split())
cnt=0
while True:
    target=(n//k)*k #나누어 떨어지는 수를 만들기 위함
    cnt+=n-target #n-target은 1로 빼는 횟수
    n=target #-1을 n-target만큼 뺐으니 이제 n값 바꿈
    if n<k:
        break
    cnt+=1
    n//=k #k로 나누기

cnt+=(n-1) #남은 수에 대해서 1빼기
print(cnt)

 

3. 오답원인

 

4. 알게된 점