[BaekJoon] 백준 1463번 풀이(1로 만들기) in Python

문제는 다음과 같다. 들어가서 확인해보시길..

 

문제 : 백준 1463번

1463번: 1로 만들기

 

알고리즘 중에서 DP, Dynamic Program를 사용하는 문제이다. DP는 DC(Divied and Conquer)와 어찌보면 비슷하지만 확연한 차이가 있다.

DP의 핵심은 문제를 세부 문제로 쪼개고 그 세부 문제들을 기억하고 있다는 점이다.

세부 문제로 쪼갠다는 것은 세분 문제들을 반복적으로 이용한다는 점에서 재귀 혹은 반복문이 사용된다는 점을 미리 인식하고 있어야한다.

또한, 기억한다는 것은 메모리 할당량이 그만큼 높아진다는 것을 의미하기 때문에 메모리 관리도 신경써야하는 부분이다.

 

이를 유념하지 않고 문제를 풀면 다음과 같다.

# 1463
import sys
import collections as co

n = int(sys.stdin.readline())

res = co.deque([n]*n)
res[0] = 0

Ndivby2 = n - 1
Ndivby3 = n - 1
flag2 = False
flag3 = False

for i in range(1,n):    # i is iter & index
    N = i + 1           # real Number
    if N % 2 == 0:
        Ndivby2 = int(N/2)
        flag2 = True
    if N % 3 == 0:
        Ndivby3 = int(N/3)
        flag3 = True

    if flag2:
        res[i] = min(res[i-1], res[Ndivby2-1]) + 1
    elif flag3:
        res[i] = min(res[i - 1], res[Ndivby3 - 1]) + 1
    elif flag2 and flag3:
        res[i] = min(res[i - 1], res[Ndivby2 - 1], res[Ndivby3 - 1]) + 1
    else:
        res[i] = res[i-1] + 1

print(res[n-1])

결론부터 말하면 이 코드는 시간초과 판정을 받았다.

이 코드의 전반적인 흐름은 1~n 까지 모든 수에 대한 결과값을 기억하고 있다가 필요한 정보를 그때그때 가져다 사용하는 코드이다. bottom-up 방식이다.

흡사 피보나치 수열을 차례대로 기억해나가면서 계산하는 흐름이라고 생각하면 되겠다.

그러면 무엇이 문제였을까?

 

시간초과 오류를 받았다는 것은 그만큼 시간복잡도(빅-오)가 컸음을 의미한다.

 

Big-O를 계산해보면,,, O(n) 만큼이 든다.

 

 

생각보다 괜찮은데?

 

 

하지만, 실제로 n = 1,000,000 을 넣고 돌렸을 때, 어마어마한 시간이 걸린다. 적어도 O(log(n))정도는 되어야 할 거 같은 느낌이다.

 

 

 

그럼 전체 탐색 말고, 재귀로 한 번 짜볼까? 그래서 나온 것이 아래 코드이다.

# 1463
import sys
import collections as co


def makeOne(n):
    res2 = res3 = n-1
    flag2 = flag3 = False

    if n == 1:
        return 0
    if n % 2 == 0:
        res2 = makeOne(n/2)
        flag2 = True
    if n % 3 == 0:
        res3 = makeOne(n/3)
        flag3 = True

    if flag2:
        return min(res2, makeOne(n-1)) + 1
    elif flag3:
        return min(res3, makeOne(n-1)) + 1
    elif flag2 and flag3:
        return min(res2, res3, makeOne(n-1)) + 1
    else:
        return makeOne(n-1) + 1


if __name__ == "__main__":
    n = int(sys.stdin.readline())

    print(makeOne(n))

코드 길이나 가독성면에서 좋아졌고 문제에 충실한 코드지만, 이 역시 시간이 어마어마하게 걸린다. 더군다나 숫자가 커질수록 stackoverflow가 발생할 가능성도 높은 위험한 코드다.