[Python] Baekjoon - 12852. 1로 만들기 2

1로 만들기 2 문제는 주어진 세 가지 연산을 이용해서 N을 1로 만드는 최소 연산 횟수와 연산 중간 과정을 구하는 문제다. 그래프 탐색 또는 다이내믹 프로그래밍 기법을 통해 해결할 수 있다. 이 글에서는 두 가지 경우의 해결방안을 모두 제시한다. 난이도는 실버 1이다.

 

백준 12852번 1로 만들기 2 문제 정보

알고리즘 분류

- 그래프 탐색

- 다이내믹 프로그래밍 (DP)

난이도

- 실버 1

1로 만들기 2 문제 요약

아래의 연산들을 사용하여 입력 N을 1로 만드는 최소 연산 횟수와 중간 숫자들(경로)을 구하는 문제다.

1. X - 1
2. X가 2로 나누어 떨어지면 2로 나누기
3. X가 3으로 나누어 떨어지면 3으로 나누기

문제 풀이 방법 1

과정

• 최소 연산 횟수를 구하는 문제이기 때문에 BFS를 사용한다.
• 각 숫자에 대해 최초 방문한 때의 연산 이전 숫자 저장한다. (경로를 구할 때 사용한다.)

풀이

• visited[x]: 숫자 X를 최초로 만들 수 있는 숫자
• getPath(): 1부터 N까지 타고 올라간 뒤, 거꾸로 경로 출력

코드

from collections import deque


def getMinOperation():
    global N, visited
    queue = deque()
    queue.append((N, 0))
    visited[N] = -1

    while len(queue) > 0:
        hereNum, hereCnt = queue.popleft()

        if hereNum == 1:
            print(hereCnt)
            return

        if hereNum % 3 == 0 and visited[hereNum//3] == 0:
            queue.append((hereNum//3, hereCnt+1))
            visited[hereNum//3] = hereNum

        if hereNum % 2 == 0 and visited[hereNum//2] == 0:
            queue.append((hereNum//2, hereCnt+1))
            visited[hereNum//2] = hereNum

        if visited[hereNum-1] == 0:
            queue.append((hereNum-1, hereCnt+1))
            visited[hereNum-1] = hereNum


def getpath():
    global N, visited
    path = [1]

    here = 1
    while here != N:
        path.append(visited[here])
        here = visited[here]

    path.reverse()
    for x in path:
        print(x, end=' ')


if __name__ == '__main__':
    N = int(input())
    visited = [0 for _ in range(N+1)]

    getMinOperation()
    getpath()

 

문제 풀이 방법 2

과정

아래의 점화식을 이용하여 푼다. (단, 2나 3으로 나누어 떨어질 때만 f(n//2), f(n//3)과 비교한다.)

• f(n) = min{f(n-1), f(n//2), f(n//3)} + 1

풀이

• dist[x]: 숫자 X로 1을 만들 수 있는 최소 연산 횟수
• path[x]: dist[x]를 만족하는 경우에 대해, x의 다음 값

코드

def getMinOperation():
    global N, dist, path

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

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

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

    print(dist[N])


def getpath():
    global N, path

    here = N
    while here != 0:
        print(here, end=' ')
        here = path[here]


if __name__ == '__main__':
    N = int(input())
    dist = [0 for _ in range(N+1)]
    path = [0 for _ in range(N+1)]

    getMinOperation()
    getpath()