[ 문제 ]

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

[ 알고리즘 유형 ]

다이나믹 프로그래밍
그래프 이론
그래프 탐색
너비 우선 탐색

[ 정답 코드 ]

from collections import deque
n = int(input())
dist = [[-1]* (n+1) for _ in range(n+1)]
q = deque()
q.append((1,0))  # 화면 이모티콘 개수, 클립보드 이모티콘 개수
dist[1][0] = 0
while q:
    s,c = q.popleft()
    if dist[s][s] == -1: # 방문하지 않았으면
        dist[s][s] = dist[s][c] + 1
        q.append((s,s))
    if s+c <= n and dist[s+c][c] == -1:
        dist[s+c][c] = dist[s][c] + 1
        q.append((s+c, c))
    if s-1 >= 0 and dist[s-1][c] == -1:
        dist[s-1][c] = dist[s][c] + 1
        q.append((s-1, c))
answer = -1
for i in range(n+1):
    if dist[n][i] != -1:
        if answer == -1 or answer > dist[n][i]:
            answer = dist[n][i]
print(answer)

[ 풀이 방법 ]

걸리는 시간의 최솟값을 구한다. 즉, 최단시간을 구해야하니 BFS로 풀면 된다.

3가지 연산만 사용해서 이모티콘을 S개 만든다
즉, 화면에 이모티콘의 개수 s와 클립보드에 있는 이모티콘의 개수c를 고려해서 풀면 된다.

1. 화면에 있는 이모티콘을 모두 복사해서 클립보드에 저장한다.
   복사 : (s,c) -> (s,s)
2. 클립보드에 있는 모든 이모티콘을 화면에 붙여넣기 한다.
   붙여넣기 : (s,s) -> (s+c, c)
3. 화면에 있는 이모티콘 중 하나를 삭제한다.
   (s,s) -> (s-1, c)
   => 모든 연산은 1초가 걸리니 모든 경로의 가중치는 1이다.
   따라서, dist[s][c] + 1 과 같이 1을 더해줘야 한다.