[실버 I] 12852번. 1로 만들기2

 문제 

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

12852번: 1로 만들기 2

 사용 언어 

Python3

 풀이 과정 

1로만들기 첫 번째 문제와 비슷하게 풀고 getpath 함수를 하나 추가해주었다.

사실 원래 풀던 방식으로는 path를 기록하는게 너무 어렵고 감이 안와서 다른 분의 코드를 참고해서 풀었다.

def getpath(x):
    global path
    current = x
    while current != 0:
        print(current, end=' ')
        current = path[current]

나한텐 살짝 어렵긴 했지만 ㅠㅠ 공부했다 치고 맞았습니다!!

음 메모리랑 시간은 높은 편 같다.

 제출 답안 

def makeOne(x):
    global count, path
    for i in range(2, x+1):
        count[i] = count[i-1] + 1
        path[i] = i-1
        if i % 2 == 0 and count[i//2] + 1 < count[i]:
            count[i] = count[i//2] + 1
            path[i] = i//2
        if i % 3 == 0 and count[i//3] + 1 < count[i]:
            count[i] = count[i//3] + 1
            path[i] = i//3

def getpath(x):
    global path
    current = x
    while current != 0:
        print(current, end=' ')
        current = path[current]

N = int(input())
count = [0 for _ in range(N+1)]
path = [0 for _ in range(N+1)]
makeOne(N)
print(count[N])
getpath(N)

 다른 사람 답안 

아무래도 더 짧은 시간이 걸린 답안을 찾아보았다. 전체적인 로직은 비슷한거같은데 deque를 사용한 것과 동적계획법이 아니라 너비우선탐색 방식을 사용한 점이 다른 것 같다. 동적계획법... 좋지만은 않을지도?

from collections import deque

N = int(input())
Q = deque([N])
visit = {N: -1}


def add(n, prev):
    if n not in visit:
        Q.append(n)
        visit[n] = prev


while Q:
    cur = Q.popleft()
    if cur == 1:
        break
    if cur % 3 == 0:
        add(cur//3, cur)
    if cur % 2 == 0:
        add(cur//2, cur)
    add(cur-1, cur)

cur = 1
path = []
count = -1
while cur != -1:
    path.append(cur)
    cur = visit[cur]
    count += 1

print(count)
print(' '.join(map(str, reversed(path))))

출처: 백준 제출현황