1로 만들기_1463

문제

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

X가 3으로 나누어 떨어지면, 3으로 나눈다.
X가 2로 나누어 떨어지면, 2로 나눈다.
1을 뺀다.
정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

입력

첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.

출력

첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

예제

예제 입력 1

2

예제 출력 1

1

예제 입력 2

10

예제 출력 2

3

문제풀이

1. 먼저, x에서부터 시작하고, x를 1로 만들기 위한 최소 연산 횟수를 저장할 리스트 (또는 배열)를 생성합니다. 이 리스트를 d라고 합니다.

2. 초기화 단계:
   d[1]은 1에서 1로 만들기 위한 연산 횟수이므로 0입니다. (즉, 이미 1이다.)
   나머지 원소들 d[2], d[3], d[4], ... 는 아직 어떤 연산도 하지 않았으므로 초기값으로 무한대(또는 충분히 큰 값)를 설정합니다.

3. 이제 2부터 x까지의 숫자에 대해 순회하면서 최소 연산 횟수를 계산합니다.

4. 각 숫자 i에 대해서, 다음 세 가지 경우 중 가장 작은 값을 d[i]에 저장합니다:
   (1) i에서 1을 뺀 경우: d[i-1] + 1
   (2) i를 2로 나눈 경우 (만약 i가 2로 나누어떨어진다면): d[i//2] + 1
   (3) i를 3으로 나눈 경우 (만약 i가 3으로 나누어떨어진다면): d[i//3] + 1

5. 위의 과정을 통해 d[x]에는 x가 1로 만들어지기 위한 최소 연산 횟수가 저장됩니다.
   이렇게 동적 프로그래밍을 사용하면 이미 계산한 중간 결과를 저장하고 필요할 때 재사용함으로써 계산 횟수를 줄일 수 있다.

이 풀이 순서를 바탕으로 코드로 구현해보자.

1. x = 1일때:

   x	1	2	3	4	5
   d[x]	0	∞	∞	∞	∞

   => d[1]은 이미 1이므로 0입니다.

나머지 d[2], d[3], d[4], d[5]는 초기값으로 무한대(또는 충분히 큰 값)을 설정합니다.

2. x=2일 때:

   x	1	2	3	4	5
   d[x]	0	1	∞	∞	∞

(1) x에서 1을 빼면 d[2] = d[2-1] + 1 = d[1] + 1 = 0 + 1 = 1입니다.
(2) x를 2로 나누면 d[2] = d[2//2] + 1 = d[1] + 1 = 0 + 1 = 1입니다. (2로 나누어떨어지기 때문에 가능)
(3) x는 3으로 나누어 떨어지지않음

=> 세 경우 중 최소값을 선택하여 d[2]에 저장

3. x = 3 일때

x	1	2	3	4	5
d[x]	0	1	1	∞	∞

(1) x에서 1을 빼면 d[3] = d[3-1] + 1 = d[2] + 1 = 1 + 1 = 2
(2) x를 2으로 나누어 떨어지지 않음
(3) x를 3으로 나누면 d[3] = d[3//3] + 1 = d[1] + 1 = 0 + 1 = 1

=> 세 경우 중 최소값을 선택하여 d[3]에 저장

4. x = 4 일 때

x	1	2	3	4	5
d[x]	0	1	1	2	∞

(1) x에서 1을 빼면 d[4] = d[4-1] + 1 = d[3] + 1 = 1 + 1 = 2
(2) x를 2로 나누면 d[4] = d[4//2] + 1 = d[2] + 1 = 1 + 1 = 2입니다.
(3) x를 3으로 나누어 떨어지지 않음

=> 세 경우 중 최소값을 선택하여 d[4]에 저장

5. x = 5 일 때

x	1	2	3	4	5
d[x]	0	1	1	1	3

(1) x에서 1을 빼면 d[5] = d[5-1] + 1 = d[4] + 1 = 2 + 1 = 3입니다.
(2) x를 2로 나누어 떨어지지 않음
(3) x를 3으로 나누어 떨어지지 않음

=> 세 경우 중 최소값을 선택하여 d[5]에 저장

나머지 값도 이와 같은 방식으로 계산하면 충분히 큰 x에 대해서도 구할 수 있을 것.

코드

import sys
x= int(sys.stdin.readline())

d=[0]*(x+1) #x의 갯수만큼 0 이담긴 리스트로 초기화
for i in range(2,x+1): 
    d[i]=d[i-1]+1 # 1을 빼는 연산 -> 1회 진행
    if i%2==0: # 2로 나누어 떨어질 때, 2로 나누는 연산
        d[i]=min(d[i],d[i//2]+1)
    if i%3==0: # 3으로 나누어 떨어질 때, 3으로 나누는 연산
        d[i]=min(d[i],d[i//3]+1)
        
print(d[x])