백준 1463 1로 만들기 - Python

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

1463번: 1로 만들기

풀이 : 

n = int(input())

a = [0]* (n+1)

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

 

다이나믹 프로그래밍의 정석인 문제가 아닐까 생각한다. 하지만 못 풀었다... 조금 이런 접근이 낯설었다.

 

우선 다이나믹 프로그램에서는 무엇을 미리 배열을 정할지를 생각해야한다.

지금까지 문제를 풀어왔을 때 계산 결과를 미리 저장해주는 방식을 써와서 접근에 실패한 것 같은데

 

기본적으로 우리가 구하는 값을 저장해주는게 편한고 이게 맞는 것 같다.

 

우리가 구해야하는건 몇 번 연산을 했는지를 구해야 하므로 a[10] = 3 이 되도록 해야하고 

a[9] a[3]  값을 미리 저장해와서 활용해야한다

 

예로 a[10] = a[9] + 1

a[9] = a[3] + 1

a[3] = a[1] + 1

a[1] = 0

거꾸로 다시 가면 a[10] = 3 이 된다.

 

중간에 min을 사용한 것은 3으로 나눌때가 더 작은 2로 나눌때가 더 작을지 케이스를 나눠준것이다.