문제

입출력

---

해설

1 2 3 4 5 6 7 8 9 10 은
0 1 1 2 3 2 3 3 2 3 번만에 해결됨

8을 왜 3번만에 해결된다고 했나?
8=7+1이니까 7의 계산횟수(3)+1인 4로 나올 수 있는데?
4에 2를 곱하면 8이 되니까. (4의 계산횟수(2)+1)

그러면 입력받은 정수N에 대해 N-1의 계산횟수와 N/2(또는 N/3)의 계산횟수를 대조하면 되는구나.

내가 230을 입력했다 치자. 그러면 229의 계산횟수와 115의 계산횟수는 어떻게 아는데?

bottom-up : 반복문을 이용해 작은것부터 해결

2의 계산횟수 , 3의 계산횟수, ..., N의 계산횟수 구하기

코드

#입력
N = int(input())

#1부터 만들어 갈 배열
arr = [0]*(N+1)

# 1의 계산횟수는 0회이다.
arr[1] = 0

# 2부터 N까지의 계산횟수를 구해보자.
for i in range(2, N+1):
    #일단 계산횟수를 이전 숫자보다 1많은 걸로 설정한다.
    arr[i] = arr[i-1]+1
    #그러나 2로 나누어떨어질 수 있다면?
    if i%2 == 0:
        #i의 절반이 되는 수의 계산횟수에 1을 더하면 된다. => arr[i/2]+1
        #그럼에도 일단 설정해놓은 계산 횟수보다 클 수 있으므로 비교해본다.
        arr[i] = min(arr[i//2]+1, arr[i])
    # 그러나 3으로 나누어떨어질 수 있다면?
    if i%3 == 0:
        arr[i] = min(arr[i//3]+1, arr[i])

# 반복문을 다 돌면 N의 계산횟수를 구할 수 있다.
print(arr[N])

#다이나믹 프로그래밍