[python][백준/BOJ] 1463번 : 1로 만들기

https://www.acmicpc.net/problem/1463

1463번: 1로 만들기

 

✅ 문제 풀이

• 처음 푸는 DP 문제라서 다른 풀이를 보고도 이해를 못했었다가 드디어 풀었다. 😎😎😎
• bottom - up , 상향식 방식으로 풀었다.
• 문제를 풀기위한 식을 세우기 위해 숫자 하나씩 필요한 최소 횟수를 생각해보자.
• 1 ➡ 0 (1은 1로 만들기 위한 횟수가 필요없으므로 횟수가 0이다.) 
• 2 ➡ 1 (2-1 이나 2//2 로 1을 만들 수 있으므로 횟수가 1)
• 3 ➡ 1
• 4 ➡ 2 (4//2 ➡ 2//2 or 2-1)
• 5 ➡ 3 (5-1 ➡ 4//2 ➡ 2//2) or (5-1 ➡ 4-1 ➡ 3//3) 방법은 다르나 최소횟수는 똑같이 3 !
• 6 ➡ 2 (6//2 ➡ 3//3)
• 7 ➡ 3
• 8 ➡ 3
• 9 ➡ 2
• 10 ➡ 3
• 10을 예시로 보면, 10 ➡ 9 ➡ 3 ➡ 1 의 과정이 최소 횟수인데, 
• 과정을 둘로 나누어 볼 수 있다.  10 ➡ (9 ➡ 3 ➡ 1) 
  • 10에서 1을 빼서 9로 갈 때의 횟수 == 1
  • 9가 1이 되는 최소 경우 (이 횟수를 미리 알고 있어야 함) == 2
• 이 과정에서 알 수 있는 점화식

f[x] = min(f[x-1], f[x//2], f[x//3]) + 1

 

✅ 최종 코드

import sys

n=int(sys.stdin.readline())
#횟수를 저장할 dp 리스트
#범위를 0~n까지가 아니라 n+1로 설정한 이유는 dp[1]을 1의 최소 횟수로 설정하기 위해서
#따라서 dp[0]은 그냥 쓰지 않는 값이다!
dp=[0 for _ in range(n+1)]

#반복문을 돌면서 2부터 n까지의 최소 횟수를 리스트에 저장한다.
for i in range(2,n+1):
    #현재 i의 최소 횟수는 1을 빼준 값으로 설정
    dp[i]=dp[i-1]+1
    #만약 i가 2의 배수일 경우, 1을 빼줘서 최소 횟수를 구한 값과 2로 나누어 최소 횟수를 구한 값을 비교해 작은 값을 저장한다.
    if i%2==0:
        dp[i]=min(dp[i],dp[i//2]+1)
    # 만약 i가 3의 배수일 경우, 2로 나누어 최소 횟수를 구한 값(이미 저장되어 있음)과 3으로 나누어 최소 횟수를 구한 값을 비교해 작은 값을 저장한다.
    if i%3==0:
        dp[i]=min(dp[i],dp[i//3]+1)
#구하고자 하는 n의 횟수를 출력함
print(dp[n])