이모티콘
백준 14226
영선이가 S개의 이모티콘을 화면에 만드는데 걸리는 시간의 최솟값 구하기.
- 영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다. 영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만들어 보려고 한다.
- 화면에 있는 이모티콘을 모두 복사해서 클립보드에 저장한다.
- 클립보드에 있는 모든 이모티콘을 화면에 붙여넣기 한다.
- 화면에 있는 이모티콘 중 하나를 삭제한다.
- 모든 연산은 1초가 걸린다. 또, 클립보드에 이모티콘을 복사하면 이전에 클립보드에 있던 내용은 덮어쓰기가 된다.
- 클립보드가 비어있는 상태에는 붙여넣기를 할 수 없으며, 일부만 클립보드에 복사할 수는 없다. 또한, 클립보드에 있는 이모티콘 중 일부를 삭제할 수 없다.
- 화면에 이모티콘을 붙여넣기 하면, 클립보드에 있는 이모티콘의 개수가 화면에 추가된다.
- 첫째 줄에 S (2 ≤ S ≤ 1000) 가 주어진다.
입출력
입력 | 출력 |
---|---|
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))
Author And Source
이 문제에 관하여(이모티콘), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@sezeom/이모티콘저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)