[그리디 4] 1이 될 때까지

과정 1. N에서 1을 뺀다.
과정 2. N에서 K를 나눈다.

과정 1, 2를 이용하여 N이 1이 되게 하는 최소 횟수 구하는 문제이다. 일단 K로 많이 나눌수록 최소 횟수가 될 가능성이 높아진다.

그리디 (탐욕법)	그리디 HINT
가장 좋은 것을 선택하는 방법이다.	최소 또는 최대 라는 단어가 많이 나온다.

앞의 예제들도 최소 또는 최대 횟수를 구하라는 문제들이 많으니, 힌트로 삼고 문제를 풀 때 이용하자.

미니 예제 1

1. 문제 설명하기.

N=17이고 K=4이다. 이런 경우 3가 나와야 한다.
최소 횟수를 count라고 지정하였다.

몫	나머지
몫을 구하는 연산자이다.	나머지를 구하는 연산자이다.
N의 값을 구하기 위함이다.	K로 나눠짐을 알기 위함이다. (나머지가 0이 되는 경우 K로 나눠짐.)
K로 나눠지는 경우, N을 K로 나눈 몫이 N이 된다.	K로 나눠지지 않는 경우, N에서 1을 뺀 수가 N이 된다.
//	%

2. 문제 풀이하기.

# 예시 1 (N=17, K=4인 경우)

N=17
K=4

count=0
while True:
    if N%K==0:
        N=N//K
        count+=1
    else:
        N-=1
        count+=1
    if N==1:
        break

print(count) # 3

미니 예제 2

1. 문제 설명하기.

N=25이고 K=5이다. 이런 경우 2가 나와야 한다.
최소 횟수를 count라고 지정하였다.

2. 문제 풀이하기.

# 예시 2 (N=25, K=5인 경우)

N=25
K=5

count=0
while True:
    if N%K==0:
        N=N//K
        count+=1
    else:
        N-=1
        count+=1
    if N==1:
        break
    
print(count) # 2

최적의 일반화

1. 문제 설명하기.

무한 반복문을 돌려서 과정 1,2를 수행하고, N=1이 되는 지점에서 반복문을 빠지도록 코드를 작성하였다.

2. 문제 풀이하기.

# 일반화

N,K=map(int, input().split())
count=0

while True:
    if N%K==0:
        N=N//K
        count+=1
    else:
        N-=1
        count+=1
    if N==1:
        break
    
print(count) # N=25, K=3인 경우 6이 나온다.

코드를 확인하기 위하여 N=25, K=3를 넣어서 돌려보니 6이 나왔다. (미니 예제 1,2도 모두 잘 돌아갔다.)

3. 책에 나와있는 최적의 일반화

저자는 과정을 2개로 나누어서 풀이하였다.

과정 1. N >= K인 경우
과정 2. N > 1인 경우

N이 K이상인 경우 과정 1을 수행하고, N이 K보다 적은 경우에는 어차피 K로 나눌 수 없기 때문에 과정 2를 수행한다.

# 책에 나와있는 일반화 방식 : 과정을 2가지로 나누어서 풀이한다.

N, K=map(int, input().split())
count=0

while N>=K: # 과정 1
    """
    if N%K==0:
        N=N//K
        count+=1
    else:
        N-=1
        count+=1
    """
    while N%K != 0: # 과정 1 (N이 K로 나눠지지 않는 경우)
        N-=1
        count+=1
    N=N//K # (N이 K로 나눠지는 경우)
    count+=1
        
while N>1: # 과정 2
    N-=1
    count+=1
    
print(count) # N=25, K=3인 경우 6이 나온다.

굳이 while 안에 while을 사용하지 않고, 조건문 if를 이용하여 풀이할 수도 있다.

# 책에 나와있는 일반화 방식 : 과정을 2가지로 나누어서 풀이한다.

N, K=map(int, input().split())
count=0

while N>=K: # 과정 1
    if N%K==0:
        N=N//K
        count+=1
    else:
        N-=1
        count+=1
        
while N>1: # 과정 2
    N-=1
    count+=1
    
print(count) # N=25, K=3인 경우 6이 나온다.