[백준] 14226번 이모티콘 (by Python)

 

문제

처음에는 떠오르는대로 BFS로 풀었지만 코드를 짜는 와중에도 뭔가 문제를 다 파악하지 못한 풀이라는 생각이 들었고, 아니나 다를까 나보다 시간을 90% 정도 절약한 분들은 Dynamic Programming을 통해 푸신 분들이었다. 간결한 코드에 끌려 원리를 고민해봤지만 수학적인 증명은 스스로 해내지 못했다. 고민해보았고, 앞으로도 더 고민해보겠지만 지금은 더 다양한 테스트 케이스에서 해당 원리가 적용된다는 확신이 없으므로 이런 유형의 문제를 만났을 때는 확실한 풀이를 먼저 시도해볼 것 같다. 좀 느릴지라도, 스스로 납득되는 코드를 짜고 싶다.

 

첫 번째 풀이 (by BFS)

from collections import deque

s = int(input())
q = deque()
next_q = deque()
visited = [False] * 2001
q.append((1, 0))
time = 0

while True:
    if not q:
        time += 1
        q = next_q
        next_q = deque()
    now, clipboard = q.popleft()
    visited[now] = True
    if s in [now + clipboard, now - 1]:
        print(time + 1)
        break
    if clipboard != 0 and (now + clipboard) < 2000:
        if not visited[now + clipboard]:
            next_q.append((now + clipboard, clipboard))
    if now != 0:
        next_q.append((now, now))
        if not visited[now - 1]:
            next_q.append((now - 1, clipboard))

보통의 BFS와 틀은 거의 유사하지만 clipboard 변수를 추가하고 visited를 확인하는 지점들이 조금 다르다. 그렇지만 뭔가 규칙을 다 발견하지 못하고 효율성을 극대화하지 못한 것 같은 찜찜함이 남아있었다.

 

두 번째 풀이 (by DP)

 

각 지점에 도착할 수 있는 최소시간을 나타낸 array를 time이라고 한다면 2 이상의 n값에 대한 time[n]은 다음 3가지 중 최솟값이라고 할 수 있다.

 

1. n

주어진 상황에서 1초를 소비해 화면에 있는 이모티콘 1개를 클립보드에 복사하여 화면의 이모티콘 수와 클립보드에 저장된 수를 각각 (1, 1) 로 만들 수 있다. 그리고 이대로 하나씩 화면에 이모티콘을 복사해나간다면 2부터의 time[n] 값은 n이 될 수 있다. 

 

2. time[n + 1] + 1

화면에 있는 것에서 한 개를 삭제하는 operation 또한 1초가 소비되므로 time[n + 1]을 구했다고 가정했을 때, time[n + 1] + 1은 time[n]의 후보가 될 수 있다.

 

3. time[k] + n / k

n의 약수 k에 대해서 time[k]에서의 화면 및 클립보드 상태는 (k, x)이고, 여기서 x는 무조건 k가 아니다. k에 최초로 도달한 시간이기 때문에 k값을 클립보드에 복사할 틈이 없었기 때문이다. 그러므로 (k, k) 상태로 만드는 데 1초가 걸리고 (i * k, k) 상태로 만드는 데에는 i초가 걸리게 된다.

 

s = int(input())
time = list(range(1003))

for i in range(2, s + 1):
    j = 2
    while i * j <= 1002:
        time[i * j] = min(time[i * j], time[i] + j)
        time[i * j - 1] = min(time[i * j - 1], time[i * j] + 1)
        j += 1

print(time[s])

 

위의 사실들을 종합하여 코드를 짰다. 그렇지만 사실 2 이상의 k에 대해 time[i]가 time[i + k] + k일 가능성을 고려하지 않는 코드이므로 논리적 허점이 있다고 할 수 있다. 물론 테스트 케이스들에서는 문제 없이 돌아갔으므로 문제 없는 논리라고 미루어 짐작할 수도 없겠지만, 증명되지 않는 이상 해당 범위에서만 운 좋게 들어맞았을 확률 역시 배제할 수 없다. 그렇기에, 난 일단 이와 같이 Bottom-Up 방식이 완벽하게 적용될 수 없는 문제에서는 확실한 탐색 방법을 먼저 시도하려고 한다. 스스로에게 납득이 되지 않는 코드는 짜고 싶지 않기 때문이다.