1463번 - 1로 만들기

세 가지 연산을 사용해서 주어진 수를 최대한 적게 연산하여 1로 만들때, 연산의 횟수를 구하는 문제입니다.

분석

이 문제는 점화식이 주어져 있다고 봐야합니다.
세 가지 연산, 3나누기, 2나누기, 1빼기를 점화식으로써 세울 수 있으면 풀이가 가능합니다.

1. 3나누기
dp(9) = dp(3) + 1 이라는 결과가 나오며, dp[i] = dp[i//3] + 1을 도출할 수 있습니다.
2. 2나누기
dp(4) = dp(2) + 1 이라는 결과가 나오며, dp[i] = dp[i//2] + 1을 도출할 수 있습니다.
3. 1빼기
dp[2] = dp[1] + 1 이라는 결과가 나오며, dp[i] = dp[i-1] + 1을 도출할 수 있습니다.

여기서 dp(N)의 결과값은 제일 적은 연산을 사용하여 N을 1로 만드는데 드는 연산수이므로, 저 세 경우 중 제일 적은 연산을 사용한 것을 하나 꼽아 현재 조사중인 수에 대입하면 되겠습니다.

점화식 : min(dp[i] = dp[i//3] + 1,dp[i] = dp[i//2] + 1,dp[i] = dp[i-1] + 1)

코딩

위의 점화식처럼 min으로 비교하여 넣는 것은 불가능하므로 하나씩 비교하며 코딩하면 됩니다.

dp = [0]*1000010

dp[1] = 0
N = int(input())

dp배열을 하나 선언해주고 N을 입력받습니다.

for i in range(2,N+1):
    dp[i] = dp[i-1] + 1

일단 1뺀 경우를 dp[i]에 넣어줍시다. 뭘 먼저하든 상관없습니다.

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

그리고 해당 3나눈 경우랑 1뺀 경우랑 비교해서 더 작은걸 dp[i]에 넣어줍니다.

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

마지막으로 2나눈 경우랑 방금 전에 dp[i]에 넣은 값이랑 비교해서 더 작은 걸 dp[i]에 넣어줍니다.

print(dp[N])

마지막으로 dp[N]을 출력해주시면 됩니다.