2022-07-10 @이영훈
접근 방법
기본적인 Dynamic Programming (DP) 문제입니다. 채점 시간 제한이 짧은 점과 memoization이 가능한 점을 통해 DP 문제임을 생각할 수 있습니다.
문제 예시에 있는 10을 생각해보면, 10 → 9 → 3 → 1로 가는 하향식 접근보다는 1 → 3 → 9 → 10으로 가는 상향식 접근이 memoization이 쉽기 때문에 저는 문제를 상향식으로 접근해서 풀었습니다.
무한으로 초기화되어 있는 dp 리스트 변수는 index가 숫자이고 안에 있는 값은 최소 몇 번 만에 만들 수 있는지에 관한 값입니다.
예를 들어 dp[1] = 0은 숫자 1은 0번만에 만들 수 있다라는 의미이고 dp[10] = 3은 숫자 10은 3번만에 만들 수 있다라는 뜻입니다.
dp[num]의 숫자와 이번에 만들 수 있는 숫자 중 최소값을 dp[num]에 업데이트하는 방식으로 접근하였습니다.
파이썬 코드
import sys
input = sys.stdin.readline
target = int(input())
INF = int(1e8)
dp = [INF] * (target + 1)
dp[1] = 0
for num in range(1, target + 1):
if num * 3 <= target:
dp[num * 3] = min(dp[num * 3], dp[num] + 1)
if num * 2 <= target:
dp[num * 2] = min(dp[num * 2], dp[num] + 1)
if num + 1 <= target:
dp[num + 1] = min(dp[num + 1], dp[num] + 1)
print(dp[target])
Python
복사
제출결과
같은 코드인데 PyPy3로 제출했을 때가 Python3로 제출했을 때보다 6배 넘게 빠르게 동작합니다
