문제

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

소스코드

from collections import deque
if __name__ == "__main__":  
    n = int(input())
    dist = [[-1] * (n+1) for _ in range(n+1)]
    q = deque()
    q.append([1,0]) #(s,c)의 현재 값
    dist[1][0] = 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])
    res = 1000000
    for i in dist[n]:
        if i != -1:
            res = min(res,i)
    print(res)

설명

• 최소값을 구하는 문제 > BFS 사용하기
• DP를 이용해서 값 저장해주기

DP를 (S,C) 의 경우의 수로 생각해서 메모이제이션 해준다. 예를 들어 (1,0) 이면 화면에 이모티콘이 한개, 클립보드에 0개인 경우이다.

이때 문제에 주어진 대로 클립보드에 복사한다면 (1,1)이되고 카운트는 1 추가되서 (1,0) 일 때 카운트에서 +1 해서 저장해준다.
(1,1) 일 때, 클립보드에 값을 화면에 붙이면 (2,1)이되고 카운트는 (1,1)일때 +1 을 해줘서 DP[2][1]에 저장해준다.

화면에 복사할 때 둘의 합이 N보다 커지면 걍 안해준다. 삭제해야하니까
화면의 이모티콘을 지울 때 그 값이 0 이면 하지 않는다. 붙여야하니까.

최종 값은 내가 구하려는 N의 행에서 가장 작은 값을 출력하면 된다.

후기

DFS로 풀었을 때 오류가 나서 도대체 왜 안되지 라고 생각했는데 왜 안되냐면 3가지 경우의 수를 모두 체크해주고 다음 3가지 경우의 수를 체크해줘야하는데 DFS로 하면 하나 체크하고 다음 DFS로 넘어가게 되니까 안됨
BFS를 이용해서 모든 경우의 수를 동일한 레벨에서 체크해주고 다음 체크 레벨로 넘어가야함

    def dfs(s,c):
        if s > 0 and arr[s][s] == -1:
            arr[s][s] = arr[s][c] + 1
            dfs(s,s) #첫번째 경우의 수만 체크하고 다음으로 넘어감
        if s + c <= n and arr[s+c][c] == -1:
            arr[s+c][c] = arr[s][c] + 1
            dfs(s+c,c) 
        if s-1 >= 0 and arr[s-1][c] == -1:
            arr[s-1][c] = arr[s][c] + 1
            dfs(s-1,c)