[백준, Python] 1463 - 1로 만들기

문제 링크

 

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.

2. X가 2로 나누어 떨어지면, 2로 나눈다.

3. 1을 뺀다.

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

 

첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.

 

---

1. 풀이

- 처음에는 BFS로 풀었다. 그런데 시간 초과가 났다.

1. DP로 풀었다. ('동적 프로그래밍'이라는 말을 쓰지만 메모이제이션이라는 말이 더 직관적인 것 같다.)

2. 글을 쓰면서 BFS 코드를 다시 봤는데, 암만 생각해 봐도 BFS 코드가 DP 코드에 비해 시간 초과가 날 부분이 없다는 생각이 들었다. 그래서 좀 더 살펴보니, 큐에 들어가는 중복값이 너무 많았다. 조건을 더 넣어서 큐에 들어가는 값의 수를 줄이니까 DP보다도 빠른 결과가 나왔다.

 

1.1. 코드(DP)

import sys
from collections import deque

input = sys.stdin.readline
N = int(input())

if N == 1:
    print(0)
elif N == 2 or N == 3:
    print(1)
else:
    lst = [0] * (N + 1)
    lst[2], lst[3] = 1, 1

    for i in range(4, N + 1):
        # 기본적으로 아무리 횟수가 많아도 lst[i]는 lst[i-1] + 1이 최대임
        lst[i] = lst[i-1] + 1
        if i % 3 == 0:
            lst[i] = min(lst[i // 3] + 1, lst[i])
        if i % 2 == 0:
            lst[i] = min(lst[i // 2] + 1, lst[i])
    
    print(lst[N])

 

1.2. 코드(BFS)

import sys
from collections import deque
input = sys.stdin.readline
N = int(input())

dct = {}
dct[1] = int(1e6 + 1)

dq = deque([]) 
dq.append((N, 0)) # N에서 출발
visited = {N: 0}

while True:
    now, depth = dq.popleft()

    if now == 1:
        print(depth)
        break

    # 1. dict의 조회 시 `in`을 쓰는 방법이 있다
    if now % 3 == 0 and now // 3 not in visited:
        dq.append((now // 3, depth + 1))
        visited[now // 3] = depth + 1

    if now % 2 == 0 and now // 2 not in visited:
        dq.append((now // 2, depth + 1))
        visited[now // 2] = depth + 1

    if now - 1 not in visited:
        dq.append((now - 1, depth + 1))
        visited[now + 1] = depth + 1

- BFS는 가까운 순서대로 방문하기 때문에 now 값이 1이 되는 가장 처음 순간의 depth 값이 정답이 된다는 장점이 있다.

- 왜 시간 초과가 뜨나 했더니, 방문 딕셔너리를 갱신하는 코드가 없었다.... 큐에 너무 많은 값이 들어가지 않도록 방지해야 한다.

- visited 에 값을 넣는 조건은 dq.popleft() 때가 아니라 dq.append() 하는 순간에 넣어준다. 큐에 중복된 값이 들어가지 않도록 한다.

- 정답이 처음 나왔을 때는, 각 조건에 추가 조건을 달았다 : depth + 1 < visited[now // 3] 일 때에만 값을 넣었는데, BFS이기 때문에 (depth + 1) > visited[now // 3] 일 수가 없다. 코드 실행 순서는 depth가 서서히 커지는 방향으로 동작하기 때문이다. 따라서 해당 코드를 제거하고 또 테스트를 돌려봤다.

 

 

위 2개가 BFS 풀이, 가장 아래가 DP 풀이다.