[백준 1463] 1로 만들기(python)

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

실버3 문제로 아주 대표적인 DP문제라고 한다.

내가 푼 방법이 너무나 비효율적이라.. 다른 풀이를 보면서 여러가지 풀이에 대해서 써보려고 한다.

나의 풀이

우선 나는 재귀를 활용한 방식으로 문제를 풀었고, DP를 활용하여 반복적인 연산을 최대한 막아보려고 했다. 재귀를 활용해 DP를 업데이트 하였고 값이 있을때 최소값으로 업데이트하고 기존보다 크면 더이상 연산하지 않도록 하였는데, 내가 푼 방법의 문제는 결정되지 않는 숫자들을 모두 채우기 위해서 노력한다는 점에서 시간이 많이 들었다.

import sys
sys.setrecursionlimit(10000000)
input = sys.stdin.readline

n = int(input())
dynamic = [1e9 for i in range(n+1)]

def dfs(n, d):
    if d < dynamic[n]:
        dynamic[n] = d
    else : 
        return
    if n%3==0:
        dfs(n//3, d+1)
    if n%2 ==0:
        dfs(n//2, d+1)
    dfs(n-1, d+1)
dfs(n,0)
print(dynamic[1])

E

결과를 보면 dynamic에 대한 결과가 모두 연산되어 업데이트 되는 과정을 거치게 된다. 이 부분을 해결하기 위해서 가장 낮은 숫자부터 채워서 올라오는 다른 방법들을 소개해보겠다.

내 풀이의 경우는 Top-Down방법으로 윗 숫자부터 업데이터가 진행이 되어가는데, 아래 풀이는 모두 Bottom-Up방식으로 이뤄지게 된다.

풀이1. 단순 반복문

for문을 활용하여, DP를 낮은 수부터 업데이트하는데, 특정 i에 대한 값은 3가지 경우중 가장 작은 값을 선택하는 그리디한 방식으로 결정이 가능하다. 아래 코드는 숫자 i를 만들기 위한 가장 작은 시행 횟수만을 선택해서 결과를 추출하는 코드이다.

import sys
input = sys.stdin.readline

n = int(input())
dynamic=[0]*(n+1) 

for i in range(2,n+1): # 낮은 수부터 업데이트
    dynamic[i]=dynamic[i-1]+1 
    if i%2==0: 
        dynamic[i]=min(dynamic[i],dynamic[i//2]+1)
    if i%3==0:
        dynamic[i]=min(dynamic[i],dynamic[i//3]+1)

print(dynamic[n])

풀이2. 재귀

재귀를 활용하는 것도 결국은 낮은 숫자부터 업데이트 하는 방식을 선택하게 된다. 하지만 위에 수식처럼 같은 뎁스의 값을 한번에 비교할 수 있는 것이 아니기 때문에, 순서가 중요하게된다. 만약 n-1를 먼저 위치 시키게 되면, -1씩 계산하는 연산을 10^6만큼 진행하기 때문에 Recursionlimit를 풀어줘야하고, 시간이 늘어나게 된다.

n=int(input())
dynamic=[0]*(n+1)
def dfs(n):
    if dynamic[n] != 0 :
        return dynamic[n]
    if n == 1:
        return 0
    if (n%3==0) and (n%2==0):
        dynamic[n]=min(dfs(n//2)+1,dfs(n//3)+1)
    elif n%3==0:
        dynamic[n]=min(dfs(n//3)+1,dfs(n-1)+1)
    elif n%2==0:
        dynamic[n]=min(dfs(n//2)+1,dfs(n-1)+1)
    else:
        dynamic[n]=dfs(n-1)+1
    return dynamic[n]
print(dfs(n))

풀이3. 직관을 활용한 점화식

가장 빠른 풀에서 활용하는 점화식을 보면, 아래와 같은 식을 사용하여 문제를 풀게 되는데

아래 식을 분석해보면, //3으로 나눠서 진행하는 것과, //2로 나눠서 진행하는 것 두 가지 중 작은 값을 선택하되, 뒤에 %3, %2로 나머지를 더함으로써 -1를 통해 늘어나는 값을 사용했다. 결국은 -1의 활용을 2 또는 3으로 나눌 수 있는 숫자로 만드는 목적으로만 사용하여 문제를 해결한 것이다.  

dp[n] = 1 + min(dfs(n // 3) + n % 3, dfs(n // 2) + n % 2)

정답 코드

n=int(input())
dp=[0]*(n+1)
def dfs(n):
    if dp[n] != 0:
        return dp[n]
    if n <= 1:
        return 0
    dp[n] = 1 + min(dfs(n // 3) + n % 3, dfs(n // 2) + n % 2)
    return dp[n]
print(dfs(n))