[python] 백준 1463번 : 1로만들기 ( 다이나믹 프로그래밍 DP)

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

1463번: 1로 만들기

 

큰 수를 3가지경우로 나누어서 가장 최단의 수로 1을 만드는 방법을 찾아야한다. 

 

이문제는  bottom-up 을 사용해서 dp로 풀면 될 것 같다.

 

이유1. 작은 수에서 구한 '최소의 해'가 큰수를 작은 수로 나누었을 때 다시 출현하게되고 그때  그 수의 '최소의 해' 를 사용한다면 무조건 최적의 해가 나온다.

 

재귀를 사용해도 구할 수 있을 것이다( dp 는항상 두가지 방향으로 구할 수 있다.)

하지만 둘다 사용이 가능하다면 조금더 빠른 반복문을 사용하고싶기 때문에(구현이 쉽기도 하고)

bottom-up 방식을 사용해서 구해보도록 하겠다.

 

( bottom-up 방식을 사용하면 굳이 구할 필요가 없는 것들을 구하게 될 수도 있겠다. top-bottom 방식을 사용하는 것도 좋아보인다-> 아래에 두개의 해설 모두 적어놓았다.)

 

 

x = int(input())

make_one = [0] *(x+1)


for i in range(2,x+1):

    third = make_one[i-1] +1
    make_one[i] = third

    if i%3 == 0 :
        one = make_one[int(i/3)] +1
        make_one[i] = min(make_one[i] , one)

    if i%2 == 0 :
        two = make_one[int(i/2)] + 1
        make_one[i] = min(make_one[i] , two )

print(make_one[x])

 

 

보다더 간결하게 적을 수 있었다.

 

n = int(input())

dp = [0 for _ in range(n+1)]

for i in range(2, n+1):
    dp[i] = dp[i-1] + 1  

    if i%2 == 0 and dp[i] > dp[i//2] + 1 :
        dp[i] = dp[i//2]+1
        
    if i%3 == 0 and dp[i] > dp[i//3] + 1 :
        dp[i] = dp[i//3] + 1
        
print(dp[n])

 

내가 이 풀이에서 고민했던 것이 2와 3을 나누는 것까지는 당연히 이해가 된다 ( 구현하기도 편하고)

하지만 어떤 방법을 통해서 최소(min) 의 값을 설정할 것인가? 에 대해서 조금 고민했다. 

 

나는 if 문 자체에는 i 에관해서(1,2 번 조건들) 을 '사용' 가능한지만 판별했다. 

하지만 시간을 더 줄이려면 그수가 '최소'인지를 if 문에서 거른다면 더 빨리 연산가능 할 것이다

오늘도 좋은 팁(?) 같은걸 배웠다. 오늘 문제는 다소 가볍기도해서 일찍 마치겠다