[백준] 1463번 1로 만들기

💡문제접근

• 2로 나누어 떨어진다면 2로 나누고 3으로 나누어 떨어진다면 3으로 나눈다. 하지만 2와 3 두 수로도 나누어 떨어지지 않는다면 1을 뺀다.
  경우에 따라서는 2와 3으로 모두 떨어지는 수라도 2로 나누는게 더 최적일 수도 있고 3으로 나누는게 더 최적일 수도 있다. 따라서 작은 숫자부터 if문에 작성해주고 전부 if문으로 돌려야 한다. 만약 if문이 아닌 elif문을 사용하면 공배수에 대해서 문제가 발생하므로 if문으로 작성해야한다.

💡예제설명

• dp[0] = 0 >>> 0을 1로 만들 수 있는 방법은 없으므로 답은 0
• dp[1] = 0 >>> 이미 1이므로 답은 0
• dp[2] = 1 >>> 2 → 1 따라서 답은 1
• dp[3] = 1 >>> 3 → 1 따라서 답은 1
• dp[4] = 2 >>> 4 → 2 → 1 따라서 답은 2
• dp[5] = 3 >>> 5 → 4 → 2 → 1 따라서 답은 3
• dp[6] = 2 >>> 6 → 3 → 1 or 6 → 2 → 1 따라서 답은 2
• dp[7] = 3 >>> 7 → 6 → 3 → 1 or 7 → 6 → 2 → 1 따라서 답은 3
• dp[8] = 3 >>> 8 → 4 → 2 → 1 따라서 답은 3

💡코드(메모리 : 38232KB, 시간 : 544ms)

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

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

    if i % 2 == 0:	
    	# dp[4] = min(dp[4], dp[2] + 1) >> 2
        dp[i] = min(dp[i], dp[i // 2] + 1)
    if i % 3 == 0:
    	# dp[15] = min(dp[15], dp[5] + 1) >> 4
        dp[i] = min(dp[i], dp[i // 3] + 1)
print(dp[N])

💡소요시간 : 14m