티스토리 뷰

알고리즘/백준

14226번 이모티콘 백준 파이썬

글을 쓰는 개발자 2020. 12. 15. 20:03
반응형

문제:www.acmicpc.net/problem/14226

 

14226번: 이모티콘

영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다. 영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만

www.acmicpc.net

고려해야 할 것은 다음과 같다.

  1. 화면에 있는 이모티콘을 모두 복사해서 클립보드에 저장한다.
  2. 클립보드에 있는 모든 이모티콘을 화면에 붙여넣기 한다.
  3. 화면에 있는 이모티콘 중 하나를 삭제한다.

이 세가지를 유의하여 방문을 하면 된다.

 

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문제 보다는 완전탐색의 느낌을 많이 느꼈던 문제 였다.

반응형
반응형
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
«   2024/12   »
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
글 보관함