[BOJ] 1463 / 1로 만들기 / Python

[BOJ] 1463 / 1로 만들기 / Python

[BOJ] 1463 / 1로 만들기 / Python

www.acmicpc.net/problem/1463

1463번: 1로 만들기

 

풀이

처음 시도는 while 문을 이용한 조건으로 작성 하였다.

X = int(input())
cnt = 0
while (1):
    if X == 1:
        break
    if X % 3 == 0:
        X //= 3    
        cnt += 1
    elif X % 2 == 0:
        X //= 2
        cnt += 1
    else:
        X -= 1

print(cnt)

하지만, 반례인 10 에서 조건에 부합하지 않는 다는것을 생각하였다.

10 -> 9 -> 3 -> 1 이 아닌 10 -> 5 -> 4 -> 2 -> 1 이 나옴

 

그래서 모든 경우를 잡기 위하여 DFS 로 작성 해 보았다.

def solution(n):
    def DFS(n, cnt):
        global res
        if n == 1:
            res = min(res, cnt)
            return
        
        if n % 3 == 0:
            DFS(n//3, cnt+1)
        if n % 2 == 0:
            DFS(n//2, cnt+1)
        DFS(n-1, cnt+1)
    DFS(n, 0)
    print(res)
    
res = 123456789
X = int(input())
solution(X)

결과는 너무나도 당연하게 시간초과.

 

DP 문제임을 생각하고 구상해 보았지만 Memorization 을 어떻게 해야 할지 구상되지 않았고

검색을 통해 참고 하였다.

 

해법은 점화식 형태로 구하는 것

점화식 : dp(N) = min( dp(N//3) + 1, dp(N//2) + 1, dp(N-1) + 1)

X = int(input())

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

for i in range(2, X+1):
    a = b = c = 123456789
    if i % 3 == 0:
        a = dp[i//3] + 1
    if i % 2 == 0:
        b = dp[i//2] + 1
    c = dp[i-1] + 1
    dp[i] = min(a, b, c)
    
print(dp[X])

 

• 시간복잡도는 for 문을 한번 순회 하므로, O(N) (역시나 DP 가 효율적이다.)

 

이렇게 list 를 이용하여 점화식으로 아래에서 부터 값을 채워나가는 것을 Tabulation 이라고 한다.

 

Memorization 과 Tabulation 의 차이 는 따로 정리 해 보았다.

 

---

참고 블로그

infinitt.tistory.com/247

백준 (boj) 파이썬 - 1463 : 1로 만들기 (DP)