(백준) 1463 : Python

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

 

1463번은 결과값 자체를 도출하는 것은 어렵지 않으나 시간 제한이 걸려있어 알고리즘 지식을 동반해 푸는 것이 핵심인 문제이다.

이 문제를 가져온 이유는 가장 최근에 공부한 Dynamic programming이 사용되는 문제이기 때문디ㅏ.

 

동적 계획법은 상향식과 하향식이 있는데, 상향식은 제일 작은 인덱스의 수부터 목표하는 값으로 향하는 것이고 반대로 하향식은 맨위의 값에서 재귀로 제일 작은 인덱스를 향하는 것이다.

 

동적 계획법은 장점 중 메모리 공간을 활용하여 시간 복잡도를 줄일 수 있다는 것을 활용해서 문제에 접근하면 된다.

이를 메모이제이션 방법이라고 한다. (값을 기억해서 문제를 푼다고 이해해두자.)

 

메모이제이션 방법으로 문제를 풀 때 항상 나올 수 있는 모든 수를 고려하여 테이블을 초기화해야한다.

ex) d = [0] * 1000

그리고 만들어 놓은 리스트에 차곡차곡 값들을 기억시켜두면 된다.(메모이제이션)

 

[문제풀이]

num = int(input())

d = [0] * (num+1)

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

 

이 문제의 핵심인 메모이제이션을 활용한 dp(상향식)임을 생각하며  문제를 풀었다.