영선이가 S개의 이모티콘을 화면에 만드는데 걸리는 시간의 최솟값 구하기.
입력 | 출력 |
---|---|
2 | 2 |
4 | 4 |
6 | 5 |
18 | 8 |
: bfs를 이용하여 세 경우에 대해 진행한다. 모든 연산은 동일하게 1초가 걸리므로 가중치 없이 append한다.
화면의 이모티콘과 클립보드의 이모티콘 개수를 2차원 배열로 함께 나타낸다.
각 경우에 대해 큐에 넣고 탐색
from collections import deque
def bfs(n, visited):
visited[1][0] = 0
q = deque()
q.append((1,0))
while q:
u, c = q.popleft()
if u==n:
return visited[u][c]
#화면 모두 복사 클립보드에 저장
if 0<=u<=n and visited[u][u] == -1:
visited[u][u] = visited[u][c]+1
q.append((u,u))
#클립보드 모두 화면으로 붙여넣기
if 0<=u+c<=n and visited[u+c][c] == -1:
visited[u+c][c] = visited[u][c]+1
q.append((u+c, c))
#화면에 있는 이모티콘 하나 삭제
if 0<=u-1<=n and visited[u-1][c] == -1:
visited[u-1][c] = visited[u][c]+1
q.append((u-1,c))
n = int(input())
#화면, 클립보드
visited = [[-1]*(n+1) for _ in range(n+1)]
print(bfs(n, visited))