BOJ/백준-1463-python

문제📖

풀이🙏

• 첫째 줄에 1보다 크거나 같고, 10^6보다 작거나 같은 정수 N이 주어진다.
• 연산은 다음과 같이 세 가지로 나뉜다.
  -> 1. 3으로 나누어 떨어지면, 3으로 나눈다.
  -> 2. 2로 나누어 떨어지면, 2로 나눈다.
  -> 1을 뺀다.
• 첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.
• 시간 제한 0.15초, 메모리 제한 128MB
  -> DP 알고리즘 문제이다.
  -> 작은거부터 큰 문제를 해결하는 오름차순 방식으로 해결해야지 시간안에 해결할 수 있다.
  -> DP 문제는 배열로 나눠서 문제를 나누어서 푸는게 수월하고좋다.

코드💻

# boj, 1463 : 1로 만들기, python
# dp : 큰 문제를 작은 문제로 나눠서 푸는 알고리즘
import sys

def DP(N):
    for i in range(2, N+1):
        d[i] = d[i-1] + 1
        
        if all((i%2==0, d[i] > d[i//2] + 1)):
            d[i] = d[i//2] + 1
        if all((i%3==0, d[i] > d[i//3] + 1)):
            d[i] = d[i//3] + 1 
    
    return d[N]
        
N = int(sys.stdin.readline())

d = [0] * (N + 1)    

print(DP(N))

결과😎

출처 && 깃허브📝

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