[백준/DP/1463] 1로 만들기

이미지 클릭시, 문제로 이동됩니닷 :)

DP

• // : 소수점 이하의 수를 모두 버리고 몫만 나타낼 때

sol1 - FAIL

import sys 

a = int(sys.stdin.readline())

nCnt = 0;
while True:
  if a == 1 :
    print(nCnt)
    break;
  elif (a%3 == 0):
    a = a//3
  elif (a%2 == 0):
    a = a//2
  else :
    a -= 1
  nCnt += 1

간단하게 조건만 사용.
힌트는 10의 경우 최솟값은3. (10 -> 9 -> 3 -> 1 로 3번)
위 코드는 4이다. (10 -> 5 -> 4 -> 2 ->1 로 4번)

sol2

import sys
input = sys.stdin.readline
n = int(input())

dp = [0 for i in range(n+2)]
dp[1] = 0
dp[2] = 1

for i in range(3, n+1):
    dp[i] = dp[i-1]+1
    if i%2 == 0:
        dp[i] = min(dp[i], dp[i//2]+1)
    if i%3 == 0:
        dp[i] = min(dp[i], dp[i//3]+1)
print(dp[n])

생각하면 쉬운데 코드 짜기가 너무 어렵다아..
문제를 많이 풀어봐야 할듯