알고리즘/백준
14226번 이모티콘 백준 파이썬
글을 쓰는 개발자
2020. 12. 15. 20:03
반응형
문제:www.acmicpc.net/problem/14226
14226번: 이모티콘
영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다. 영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만
www.acmicpc.net
고려해야 할 것은 다음과 같다.
- 화면에 있는 이모티콘을 모두 복사해서 클립보드에 저장한다.
- 클립보드에 있는 모든 이모티콘을 화면에 붙여넣기 한다.
- 화면에 있는 이모티콘 중 하나를 삭제한다.
이 세가지를 유의하여 방문을 하면 된다.
|
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
|
import sys
from collections import deque
S=int(input())
visited=[[-1]*3001 for _ in range(3001)]
def bfs(left,right):
q=deque()
q.append([left,right])
visited[left][right]=0
while q:
emoti,clip=q.popleft()
if emoti==S:
break
if clip:
if visited[emoti+clip][clip]==-1 and emoti+clip<=S:
visited[emoti+clip][clip]=visited[emoti][clip]+1
q.append([emoti+clip,clip])
if visited[emoti][emoti]==-1:
q.append([emoti,emoti])
visited[emoti][emoti]=visited[emoti][clip]+1
if visited[emoti-1][clip]==-1 and emoti-1>0:
visited[emoti-1][clip]=visited[emoti][clip]+1
q.append([emoti-1,clip])
else:
q.append([emoti,emoti])
visited[emoti][emoti]=visited[emoti][clip]+1
bfs(1,0)
ans=10e9
for i in range(S+1):
if visited[S][i]!=-1:
ans=min(ans,visited[S][i])
print(ans)
|
cs |
화면에 있는 이모티콘을 모두 복사해서 클립보드에 저장한 방법은 if문 2번째, 클립보드에 있는 모든 이모티콘을 화면에 붙여넣기 한 것은 1번째, 화면에 있는 이모티콘 중 하나를 삭제하는 것은 마지막이다.
else는 처음에 1이 아니면 무조건 화면에 있는 이모티콘을 모두 복사해서 클립보드에 저장하는 것이다.
이 문제를 풀면서 bfs문제 보다는 완전탐색의 느낌을 많이 느꼈던 문제 였다.
반응형