BOJ - 1463

백준 문제 링크
1로 만들기

❓접근법

1. DP = [0] * (N+1)으로 설정하고,
   DP[1] = 0
   DP[2] = 1로 지정한다.
2. range(3, N+1)동안

• DP[i] = DP[i-1] + 1 # 이 경우는 1을 뺀 경우
• if i % 3 == 0이면
  • DP[i] = min(DP[i], DP[i // 3] + 1) # 이 경우는 3으로 나눈 경우
• if i % 2 == 0이면
  • DP[i] = min(DP[i], DP[i // 2] + 1) # 이 경우는 2로 나눈 경우
  3. 위에서 나눴을 때 min 함수를 사용하는 이유는,
     예를 들어 N = 10일 때 위 min 함수를 사용하지 않으면
     [0, 0, 1, 1, 2, 3, 2, 3, 3, 2, 4]에서, 4로 나타나게 된다.
  4. 10으로 가는 법은 9의 가짓수에서 1만 더하면 되므로
     3이 최소 가짓수일텐데 여기서 4로 나타났다.
     그 이유는 처음 1을 뺀 경우가 3, 2로 나눈 경우가 4 이지만
     (3, 4) 중 최솟값을 저장하지 못했기 때문이다.
     따라서 최솟값을 저장하기 위해 min을 사용해야한다.

👌🏻코드

N = int(input())


if N == 1:
 print(0)
 
elif N == 2:
 print(1)
 
else:
 DP = [0] * (N+1)
 DP[1] = 0
 DP[2] = 1
 
 for i in range(3, N+1):
     
     DP[i] = DP[i-1] + 1
     
     if i % 3 == 0:
         DP[i] = min(DP[i], DP[i // 3] + 1)
         
     if i % 2 == 0:
         DP[i] = min(DP[i], DP[i // 2] + 1)
         
 print(DP[N])