[백준] 1463번 : 1로 만들기 (Python)

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

 

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

 

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 사용해 1을 만드는 연산의 최솟값을 구하는 문제.

 

import sys

input = sys.stdin.readline

N = int(input()) # 구하고자 하는 수
D = [0 for j in range(N+1)] # DP 리스트
D[1] = 0 # 1일 때 연산 불필요
  
# 조합 점화식으로 DP 테이블 채워넣기
for i in range(2, N+1):
    D[i] = D[i-1]+1 # -1 연산 표현
    
    if(i%2==0): # if 2의 배수
        D[i] = min(D[i], D[i//2]+1) # 나누기 2 연산
        
    if(i%3==0): # if 3의 배수
        D[i] = min(D[i], D[i//3]+1) # 나누기 3 연산

print(D[N])

 

 

[문제풀이]

---

1. 기본적으로는 이전 연산에서 +1 횟수
2. 2로 나누어떨어지면 2로 나눈 값에서 +1
3. 3로 나누어떨어지면 3로 나눈 값에서 +1

 

2와 3의 경우는 이미 저장된 값이 더 작은가 확인해서 하면 끝난다.