1로 만들기

❓문제
[https://www.acmicpc.net/problem/1463]](https://www.acmicpc.net/problem/1463)

❗문제 정리
📑코드

n=int(input())
dp=[0]*1000001

for i in range(2, n+1):
    dp[i]=dp[i-1]+1#이전 연산수와 지금하는 연산수 더함.
    if i%2==0:
        dp[i]=min(dp[i],dp[i//2]+1)#+1의 목적은 계산 수 누적해주기 위함.
    if i%3==0:
        dp[i]=min(dp[i],dp[i//3]+1)

print(dp[n])

📝코드 설명

n=int(input())
dp=[0]*1000001

최대 10^6까지 입력받을 수 있다하여 0을 포함한크기인 10000001 크기의 0으로 채워진 dp테이블을 만든다.
이 테이블을 채우는 값은 연산한 횟수이다.

for i in range(2, n+1):
    dp[i]=dp[i-1]+1#이전 연산수와 지금하는 연산수 더함.
    if i%2==0:
        dp[i]=min(dp[i],dp[i//2]+1)#+1의 목적은 계산 수 누적해주기 위함.
    if i%3==0:
        dp[i]=min(dp[i],dp[i//3]+1)

dp[i//2]+1 dp[i//3]+1의 목적은 가장 최근에 2 또는 3으로 나눈연산수를 가져오기 위함.
최소의 연산횟수를 찾아야하므로 min 사용.

🎖제출 결과

💡insight
이코테-다이나믹 프로그래밍