[백준/python] 1463 - 1로 만들기(DP)

문제: https://www.acmicpc.net/problem/1463

 

사용 알고리즘: DP

 

 

할 수 있는 연산

- 1 빼기

- 2로 나누기

- 3으로 나누기

 

 

나는 dp 문제를 풀 때 잘 모르겠으면 손으로 써가면서 규칙을 찾아 점화식을 쓰는 편인데 이번 문제도 쓰면서 풀다보니 규칙이 보였다.

 

dp[1] = 0

 -> 1 은 아무 연산을 하지 않아도 1 이기 때문에 연산 횟수는 0

dp[2] = 1

 -> 2 는 2-1 또는 2//2 를 해서 1 로 만들 수 있고 최소 연산 횟수는 1

dp[3] = 1

 -> 3 은 3//3 을 해서 1로 만들 수 있고 최소 연산 횟수는 1

 

dp[4]: 4 -> 2 -> 1

dp[5]: 5 -> 4 -> 2 -> 1

dp[6]: 6 -> 2 -> 1

dp[7]: 7 -> 6 -> 2-> 1

dp[8]: 8 -> 4 -> 2 -> 1

dp[9]: 9 -> 3 -> 1

dp[10]: 10 -> 9 ->  3 -> 1 

dp[11]: 11 -> 10 -> 9 -> 3 -> 1

dp[12]: 12 -> 4 -> 2 -> 1

 

※ 참고

2, 3 으로 모두 나눠떨어지는 6 의 배수는 2 말고 3 으로 나누면서 계산을 해줘야 하는데, 2 보다 3 이 크기 때문에 나누었을 때 더 작은 수가 남기 때문에 더 적은 연산 횟수가 든다. 

 

여기까지 써보면 규칙을 확인할 수 있다. 

 

- 1 과 자기자신으로 밖에 나눠지지 않는 소수들은 (바로 전 숫자의 연산횟수 + 1)

- 소수를 제외한 수들은 (2 또는 3 으로 나눴을 때의 몫인 숫자의 연산횟수 + 1)

 

 

ex) dp[8] = dp[8//2] + 1 = dp[4] + 1

       dp[4]: 4-> 2 -> 1, dp[8]: 8 -> 4 -> 2 -> 1

 

       dp[9] = dp[9//3] + 1 = dp[3] + 1

       dp[3]: 3-> 1, dp[9]: 9 -> 3 -> 1

 

       dp[12] = dp[12//3] + 1 = dp[6] + 1

       dp[6]: 6 -> 2 -> 1, dp[12]: 12 -> 6 -> 2 -> 1

 

       dp[5] = dp[5-1] + 1 = dp[4] + 1

       dp[4]: 4 -> 2 -> 1, dp[5]: 5 -> 4 -> 2 -> 1

 

 

하지만 10 은 조금 예외적인 경우로 2로 나눠지지만 1 을 먼저 빼는 것이 더 적은 연산횟수가 든다.

 

ex) dp[10] = dp[10//2] + 1 = dp[5] + 1 = 3 + 1 = 4

      dp[5]: 5 -> 4 -> 2 -> 1, dp[10]: 10 -> 5 -> 4 -> 2 -> 1

 

       dp[10] = dp[9] + 1 = 2 + 1 = 3

       dp[9]: 9 -> 3 -> 1, dp[10]: 10 -> 9 -> 3 -> 1

 

 

그래서 i 번째 수를 1로 만들기 위한 최소 연산 횟수를 구하려면 아래의 경우를 고려해야 한다. 

 

- 3 의 배수인 경우: dp[i] = min( 1을 먼저 빼는 경우, 3 으로 나누는 경우)

- 2 의 배수인 경우: dp[i] = min(1을 먼저 빼는 경우, 2 로 나누는 경우)

- 소수인 경우: dp[i] = 1을 먼저 빼는 경우

 

세 가지 경우를 모두 고려하여 코드를 짜면 아래와 같이 코드를 짤 수 있는데, if 문의 순서를 바꾸면 답이 틀려지니 주의하자.

 

 

※ 참고

위에서 2, 3 으로 모두 나눠지는 수는 더 큰 수인 3 으로 나누는 것이 이득이라고 하였는데, 2, 3 으로 모두 나눠지는 수가 for 문을 돌 때 2 로 나눠지는 경우를 먼저 구해서 dp[i] 값을 구하게 되고 그 다음 if 문에 들어가게 된다. 그러면 결국 최종 값은 3 으로 나눠지는 경우로 dp[i] 값이 갱신되기 때문에 문제가 없는데, if 문의 순서를 바꾸면 최종값이 2 로 나눠지는 수로 갱신되기 때문에 값이 달라져 문제가 생긴다.

 

import sys

n = int(sys.stdin.readline())

dp = [0] * 1000001

dp[1] = 0
dp[2] = 1
dp[3] = 1

for i in range(4, n+1):
    dp[i] = dp[i-1] + 1

    if i % 2 == 0:
        dp[i] = min(dp[i], dp[i//2] + 1)
    if i % 3 == 0:
        dp[i] = min(dp[i], dp[i//3] + 1)


print(dp[n])