[BOJ][python] 12852. 1로 만들기 2

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

12852번: 1로 만들기 2

---

💡IDEA

DFS 또는 동적 계획법을 사용하는 문제이다.

1463. 1로 만들기 문제와 거의 동일한데, N을 1로 만드는 방법에 포함된 수를 출력해야 한다는 점이 달랐다.

1463번에서 사용했던 그대로 DFS를 수행하지만 왔던 길을 기억하는 path를 저장했다.

N에서 세가지 방법으로 1을 만들었을 때 연산 횟수의 최솟값을 갱신하는 과정에서 path도 갱신해주면 된다.

문제 분류에 동적 계획법도 있어서 한 번 도전해보았는데, 메모리도 시간도 꽤나 많이 잡아먹어서 DFS로 푸는 쪽이 좋을 것 같다. 그래도 두가지 풀이를 함께 적어둔다.

동적 계획법으로 푼 풀이는 연산 횟수와 연산 수를 저장할 배열을 함께 dp에 저장하는 식으로 구성했다. 세가지 연산 방법에 대해서 연산하기 전의 dp에 대해 개수를 +1 해주고 연산한 수를 배열에 추가해주었다. 이렇게하면 마지막 N번째 dp의 0번째 값은 연산 횟수의 최솟값, 1번째 값은 연산 수들의 배열이 된다. 하지만 이 배열에는 1이 저장되어 있지 않기 때문에 추가해주는 것을 주의해야 한다.

 

📌CODE

N = int(input())

def dfs(n, cnt, p):
    global ans, path
    if ans < cnt:
        return
    if n == 1:
        if ans > cnt:
            ans = cnt
            path = p
        return
    if n % 3 == 0:
        dfs(n//3, cnt+1, p+[n//3])
    if n % 2 == 0:
        dfs(n//2, cnt+1, p+[n//2])
    dfs(n-1, cnt+1, p+[n-1])

ans = 10**6
path = []

dfs(N, 0, [N])

print(ans)
print(*path)

N = int(input())
dp = [[0, []] for _ in range(N + 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[-1][0])
print(*(dp[-1][1][::-1] + [1]))