풀이과정
재귀함수로 접근할 수 있으나, 시간 제한으로 인해 문제를 해결할 수는 없다.
따라서, 다이내믹 프로그래밍(배열을 통해 반복되는 계산을 최소화)를 이용하여 문제를 해결한다.
답안
N=int(input())
d=[0 for _ in range(N+1)]
for i in range(2,N+1):
d[i]=1+d[i-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])
자세한 설명
정수 N을 받아오고, N+1개의 0으로 이루어진 배열을 생성한다.
2부터 N이 될때까지(1이 주어졌을 경우 연산을 수행하지 않아도 되므로 1은 반복문에서 제외한다.) 주어진 수는 이전 수 + 1의 연산 수를 가지는데, 주어진 수가 2 혹은 3으로 나누어질 경우 각각 조건문을 걸어준다.
만약 N이 6이라고 가정한다면, 연산 과정은 다음과 같다.
정수 2부터 6까지 반복문을 실행한다.
i가 2일 경우,d[2]는 d[2]와 d[1]+1 둘 중의 최솟값이다.
d[2]와 d[1]+1은 모두 1이므로, d[2]는 1이다.
i가 3일 경우, d[3]는 d[3]과 d[1]+1 둘 중의 최소값이다.
d[3]은 2, d[1]+1은 1이므로, d[3]은 1이다.
i가 4일 경우, d[4]는 d[4]와 d[2]+1 둘 중의 최소값이다.
d[4]는 2, d[2]+1은 2이므로 d[4]는 2이다.
i가 5일 경우, 5는 2와 3 어느 것으로도 나누어 떨어지지 않는다.
따라서 d[5]는 d[4]+1인 3이다.
i가 6일 경우 , 6은 2와 3으로 모두 나누어 떨어진다.
따라서 d[6]은 d[6]과 d[3]+1,d[2]+1 중 최솟값이다.
d[6]은 4, d[2]+1은 2, d[3]+1은 2이다. 따라서 d[6]은 2가 된다.