백준 12852 파이썬

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

12852번: 1로 만들기 2

 

 

정답 코드 (속도 빠름)

def solution():
    visited = []
    queue = [[N, [N]]]

    while queue:
        number, path = queue.pop(0)
        if number == 1:
            print(queue)
            print(len(path) - 1)
            print(" ".join(map(str, path)))
            break

        if number not in visited:
            visited.append(number)
            if number % 3 == 0:
                queue.append([number // 3, path + [number // 3]])
            if number % 2 == 0:
                queue.append([number // 2, path + [number // 2]])
            queue.append([number - 1, path + [number - 1]])


N = int(input())
solution()

 

아래에 속도가 비교적 느린 정답 코드와 비교했을 때, 위 코드는 visited 배열을 이용하여 한번 연산한 값을 체크한다. 그리하여 반복적인 연산을 막는데, 아래 코드는 visited 로 확인하는 대신, 기존의 연산 값( 아래 코드 기준 dp[i][0])이  새로 계산 한 값보다 작으면 업데이트 하는 방법을 택했다. 즉 이미 방문한 숫자에 대해서도 매번 비교 연산을 수행하기 때문에 위의 코드보다 속도가 떨어지는 것이라 생각한다.

 

 

정답 코드 (속도 느림)

N = int(input())
dp = [[0, []] for _ in range(N + 1)]
dp[1][1] = [1]

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

    if i % 3 == 0 and dp[i // 3][0] + 1 < dp[i][0]:
        dp[i][0] = dp[i // 3][0] + 1
        dp[i][1] = dp[i // 3][1] + [i]

    if i % 2 == 0 and dp[i // 2][0] + 1 < dp[i][0]:
        dp[i][0] = dp[i // 2][0] + 1
        dp[i][1] = dp[i // 2][1] + [i]

print(dp[N][0])
print(*dp[N][1][::-1])

 

 

틀린 풀이 (내 코드 ㅠ)

잘못 생각한 점이 재귀 함수의 매개변수로 queue 를  n 과 분리하여 넣은 것이다.

재귀로 함수를 호출하니 queue도 멀티스레드 마냥 개별로 생성될 것이라 생각했는데 그렇게 될 리가 없다.

매번 재귀마다 queue 에 값이 append 되기 때문에 , 각 숫자 n 에 대한 history 가 남지 않고, 모두 합쳐진 history 가 남게 되어 오답에 이르게 됐다. 즉 이런식으로 풀고 싶었다면 재귀 함수의 인자로 n 과 queue 를 하나로 묶어서 던져야한다. 

from sys import stdin

read = stdin.readline
n = int(read())
dp = [0] * (n + 1)
queue = [n]
def recursive(n, queue):
    if n < 1:
        return False
    if n == 1:
        return [n, queue]
    if n % 3 == 0:
        a = n // 3
        dp[a] = dp[n] + 1
        queue.append(a)
        recursive(a, queue)
    if n % 2 == 0:
        a = n // 2
        dp[a] = dp[n] + 1
        queue.append(a)
        recursive(a, queue)
    a = n - 1
    queue.append(a)
    return recursive(a, queue)
answer = recursive(n, queue)