1️⃣ 서론
백준 문제 14226번 이모티콘 입니다. 파이썬(Python)으로 풀었습니다.
2️⃣ 문제 설명
이모티콘을 만드는 데 걸리는 시간을 최소화 하는 문제입니다.
영선이는 다음과 같은 방법으로 이모티콘의 개수를 늘리거나 줄일 수 있습니다.
- 화면에 있는 이모티콘을 모두 복사해서 클립보드에 저장한다.
- 클립보드에 있는 모든 이모티콘을 화면에 붙여넣기 한다.
- 화면에 있는 이모티콘 중 하나를 삭제한다.
모든 연산은 1초가 걸립니다.
3️⃣ 풀이
이 방법의 풀이는 BFS를 이용하는 것입니다.
1초마다 세가지 연산을 수행하며 1초씩 증가시켜 나가면서 답이 나올때 해당 초를 출력하고 프로그램을 끝내면 됩니다.
여기서 중요한 것은 해당 이모티콘의 개수를 방문했는지의 여부가 중요합니다.
해당 이모티콘의 개수를 이미 방문했다면 더 빠른시간안에 해당 이모티콘을 만들 수 있다는 뜻이 됩니다.
따라서 방문한 이모티콘은 또다시 방문하지 않습니다.
그럼 소스코드 보시겠습니다.
4️⃣ 소스코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
from collections import deque
n = int(input())
clipboard = 0
q = deque([[1, 0]])
vis = [[0] * 1001 for i in range(1001)]
vis[1][0] = 1
if n == 1:
print(0)
exit()
count = -1
while q:
count += 1
# bfs 수행
for _ in range(len(q)):
emoticon, clipboard = q.popleft()
if emoticon == n:
print(count)
exit()
# 화면에 있는 이모티콘을 모두 복사해서 클립보드에 저장한다.
# 클립보드에 이모티콘을 복사하면 이전에 클립보드에 있던 내용은 덮어쓰기가 된다.
if not vis[emoticon][emoticon]:
q.append([emoticon, emoticon])
vis[emoticon][emoticon] = 1
# 클립보드가 비어있는 상태에는 붙여넣기를 할 수 없으며, 클립보드에 있는 모든 이모티콘을 화면에 붙여넣기 한다.
if 1 <= emoticon + clipboard <= n and not vis[emoticon + clipboard][clipboard]:
q.append([emoticon + clipboard, clipboard])
vis[emoticon + clipboard][clipboard] = 1
# 화면에 있는 이모티콘 중 하나를 삭제한다.
if emoticon - 1 >= 0 and not vis[emoticon - 1][clipboard]:
q.append([emoticon - 1, clipboard])
vis[emoticon - 1][clipboard] = 1
5️⃣ 마치며..
질문과 지적은 환영합니다. 이 문제는 최적의 정답일 수도 아닐수도 있습니다.
궁금한게 있으시면 아래 댓글 남겨주세요.🙏
댓글은 저에게 큰 힘이 됩니다!
감사합니다. ❤️
