백준1463 문제 보러가기

문제

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

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

입력

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

출력

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

예제 입력 1

2

예제 출력 1

1

예제 입력 2

10

예제 출력 2

3

힌트

10의 경우에 10 → 9 → 3 → 1 로 3번 만에 만들 수 있다.

문제 해결

점화식 만들기

이번에도 DP문제다. 여전히 DP문제는 점화식을 찾기 위해서 규칙을 찾아야한다.
이 때까지 풀었던 DP문제들과 달라서 헷갈렸다.

그런데, 조금 고민을 했고, 규칙을 찾았다.

1의 최소 횟수
0
2의 최소 횟수
1
3의 최소 횟수
1
4의 최소 횟수
2
5의 최소 횟수
3
6의 최소 횟수
2
7의 최소 횟수
3
8의 최소 횟수
3
9의 최소 횟수
2
10의 최소 횟수
3

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

해당 규칙은 다음과 같은 원리로 생성되었다.
1은 그대로 1이기 때문에 연산이 필요없어서 0번이다.
dp[1] = 0
2는 2에서 2로 나누면 되기 때문에 1번이다.
dp[2] = 1
3은 3에서 3으로 나누면 되기 때문에 1번이다.
dp[3] = 1
이제 그 다음부터는 4는 2로 나누어지기 때문에 연산 (2)이 가능하다. 따라서 dp[2]에서 연산이 한 번 추가 된 것이다. 그리고 연산 (3)도 가능하다. 따라서 dp[3]에서 연산이 한 번 추가된다. dp[2], dp[3] 모두 1로 최소값은 1이기 때문에 +1하면 dp[4] = 2 가 된다.

dp[i]에서 i가 3으로 나눠떨어지면 dp[i//3]을 한 list에 append 하고, i가 2로 나눠떨어지면 dp[i//2]를 list에 append 한다. 그리고 i는 무조건 i>=0을 만족하기 때문에 dp[i-1]도 list에 append 한다.
list 원소 중에 최소값에다가 +1해서 dp[i]로 선언하면 된다.
코드는 다음과 같다.

n = int(input())

dp = [0] * (n+1)

for i in range(1, n+1) :
    if i == 1 :
        dp[i] = 0
    elif i == 2 :
        dp[i] = 1
    elif i == 3 :
        dp[i] = 1
    else :
        check = []
        if i % 3 == 0 : # 3으로 나눠떨어지면
            check.append(dp[i//3])
        if i % 2 == 0 : # 2로 나눠떨어지면
            check.append(dp[i//2])
        check.append(dp[i-1])
        
        dp[i] = min(check)+1
        # check 리스트 원소 중에 최소값을 찾아서 +1 해서 dp[i]를 선언한다.
        
print(dp[n])