1로 만들기 - 실버 3

n = int(input())
d = [0] * (n + 1)
for i in range(2, n + 1):
    d[i] = d[i - 1] + 1
    if i % 3 == 0:
        d[i] = min(d[i], d[i // 3] + 1)
    if i % 2 == 0:
        d[i] = min(d[i], d[i // 2] + 1)
print(d[n])

 

일단 dp에는 2부터 시작하여 2에서 일을 뺀 수인 1이 들어가야한다. 그 값은 원래 모두 0인 인덱스에서 dp[2-1]인 값에 +1을 하여 들어가게 되고 이후부터는 그 전 값에 1이 더해진 값이 들어가게 된다.

 

즉 2 인덱스는 1, 3 인덱스는 2, 4 인덱스는 3인 형식이다.

 

이후 만약 i 가 3으로 나누어진다면 3으로 나누어진 인덱스의 값에 나누기를 실행한 값인 1을 더한 값과 1로 다 뺐을 때의 값으로 초기화된 값 중 뭐가 더 작은지 확인한다.

 

2도 나눠지면 같은 과정을 반복한다.

 

둘 다 if인 이유는 3으로 나눴을때 보다 2로 나눴을때 나누는 횟수가 더 작아지는 경우도 생각해줘야하기 때문이다.  

 

ex) 6을 생각해보자 dp[6] = 5로 초기화 되어 있으나 dp[6//3] = 1이다. 이에 1을 더한 값인 2가 dp[6]에 들어간다.

6은 2로도 나누어진다. dp[6//2] = 2 + 1 = 3이기 때문에 dp[6]은 여전히 2이다. 하지만 값이 올라갈 수록 2로 나누었을때 계산하는 값이 나올 확률이 생기기 때문에 꼭 if를 둘 다 넣어줘야 한다.