[백준14226] 이모티콘

문제

---

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

14226번: 이모티콘

생각의 흐름

---

결국 최종적으로는 화면에 n개의 이모티콘이 있어야 하는데 이 때, 클립보드에 있는 이모티콘의 갯수가 0~n-1개 일때중에서 어느 경우의 cost가 최소인지를 찾아야 한다는 점에 착안하여 BFS를 사용해야 한다는 것을 알 수 있다.(참고: 클립보드에 있는 이모티콘의 수는 항상 화면의 수보다 작거나 같다. 그런데 화면에 n개의 이모티콘이 있는 경우 마지막으로 클립보드에 복사하는 것은 불필요하기 때문에 상한선이 n이 아닌 n-1이 되는 것!!!)

코드에서 사용한 d[s][c]는 화면상에 s개의 이모티콘이 있고, 클립보드에 c개의 이모티콘이 있을 때 걸리는 시간값을 담고 있다. queue를 사용하여 매 s와 c의 값에 따라 갱신을 해주면 된다.

구현을 할 때에는 복사, 붙여넣기, 삭제의 세 가지 경우에 대한 것을 고려해주어야 하는데 이에 대한 각각의 상황은 코드에 주석으로 구분해 두었으니 참고하면 된다.

깨달은 점

---

의외로 이러한 cost의 최솟값을 구하는 문제에서 BFS를 사용해야 하는 경우가 많다. 그런데 그래프가 주어지고 전형적인 BFS를 사용하는 문제가 아닌 경우 BFS 알고리즘을 사용해야 한다는 것을 알아내기가 어렵다...... 

나름의 생각으로 결론을 내보자면

1. 최종단계에 도달해서도 여러 경우의 수가 있고 그 중에서 최솟값을 구해야 하는 경우

2. 최솟값을 결정짓는 요인이 한 가지가 아니어서(주로 2가지) 2차원 리스트를 직접 구현하고 갱신해가면서 결과값을 찾아야 하는 경우

위와 같은 경우에 주로 BFS를 사용하여 구현을 해야 하는 것 같다.

코드

---

import queue

n = int(input())
d = [[-1]*1001 for i in range(1001)]
d[1][0] = 0
q = queue.Queue()
q.put((1,0))

while q.qsize():
    s, c = q.get()

    # 복사
    if d[s][s]==-1:
        d[s][s]=d[s][c]+1
        q.put((s,s))
    # 붙여넣기
    if s+c<=n and d[s+c][c]==-1:
        d[s+c][c]=d[s][c]+1
        q.put((s+c,c))
    # 삭제
    if s-1>=0 and d[s-1][c]==-1:
        d[s-1][c]=d[s][c]+1
        q.put((s-1,c))

# 화면에 이모티콘이 n개이면서 클립보드에 있는 이모티콘 수가 0~n-1개 일때 중에서 최솟값
ans=-1
for i in range(n):
    if d[n][i]!=-1:
        if ans==-1 or ans>d[n][i]:
            ans=d[n][i]
print(ans)