0927_Algorithm_1463_1로만들기

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

초기 구상과정

• 나누어 떨어지면, -1을 한다 등의 조건을 처리하기에는 너무 많다. 반대로 뒤집자
• 1에서부터 원하는 숫자를 만들자!
• 최솟값을 출력하는건 어떤 방식으로 해야할까?
• 동전 나누기의 방식을 좀 차용하자

초기 코드

import sys
input = sys.stdin.readline

num = int(input())
dp = [1000001] * (num + 1)
dp[1] = 0

for i in range(1, num + 1):
    if dp[i] != 1000001:
        # if i + 1 == num or i * 2 == num or i * 3 == num: break
        if i + 1 <= num:
            dp[i + 1] = min(dp[i] + 1, dp[i + 1])
        if i * 2 <= num:
            dp[i * 2] = min(dp[i] + 1, dp[i * 2])
        if i * 3 <= num:
            dp[i * 3] = min(dp[i] + 1, dp[i * 3])
print(dp[num])

주석 처리된 부분은 저렇게 for문을 빠져나가니 다른 경우의 수에서 최적해를 구하는 과정 또한 무시해버리기 때문에 문제가 생긴다는 점이 발견되어 저렇게 처리했다.
모두 전개해나가면서 기존에 지나가며 값이 저장되어 있는 경우 새로운 값과 비교하여 더 작은 값을 저장하는 것이 핵심이다.
답은 해결했다. 그런데 궁금한 점이 하나 생겼다.

import sys
input = sys.stdin.readline

num = int(input())
dp = [-1] * (num + 1)
dp[1] = 0

for i in range(1, num + 1):
    if dp[i] != -1:
        # if i + 1 == num or i * 2 == num or i * 3 == num: break
        if i + 1 <= num:
            if dp[i + 1] != -1:
                dp[i + 1] = min(dp[i] + 1, dp[i + 1])
            else:
                dp[i + 1] = dp[i] + 1
        if i * 2 <= num:
            if dp[i * 2] != -1:
                dp[i * 2] = min(dp[i] + 1, dp[i * 2])
            else:
                dp[i * 2] = dp[i] + 1
        if i * 3 <= num:
            if dp[i * 3] != -1:
                dp[i * 3] = min(dp[i] + 1, dp[i * 3])
            else:
                dp[i * 3] = dp[i] + 1

print(dp[num])

이것도 마찬가지 방식을 사용해서 문제를 풀었다. 그런데 첫번째는 1136ms, 두번째는 1076ms의 실행시간을 보였다. dp치고는 시간도 많이 걸려서 신기했는데 첫번째 코드가 더 짧은 코드인데 왜 시간이 더 걸리는 걸까? 무턱대고 min을 계속해서 쓰니까 의미없는 경우에서도 min 함수를 쓰는 것 때문에 더 시간이 걸린다고 예상하고 있다.

느낀점

DP도 시간이 많이 걸리는 경우도 있구나. 이를 해결하기 위해서는 무엇을 해야할까?
또 다른 사람들의 정답들을 보니 memoization이 미친 성능을 보여주는데 한 번 구현해 봐야겠다.