새로운 블로그로 이전 작업을 진행하고 있어 포스트가 새로 작성되고 있지 않습니다.

빠른 시일 내에 새로운 블로그로 인사드리겠습니다.

새로운 블로그 : https://unho.vercel.app/

본문 바로가기
알고리즘 문제풀이/Python

[백준] 14226 이모티콘

by 언호 2022. 7. 13.

📖 문제


🧑🏻‍💻 풀이 과정

1) 문제 접근 및 이해

한번의 연산이 발생할 때, 세가지의 방법 중 하나로 연산이 일어났습니다.

BFS를 이용하여 현재 이모티콘, 클립보드 길이의 상황에서 세가지 연산을 모두 큐에 추가하여 탐색을 이어나갔습니다.

 

한번 탐색한 경우는 추가 탐색을 하지 않기 위하여 탐색 여부를 확인하였습니다.

탐색 여부는 딕셔너리 형태를 이용하였고, 키 값으로는 (이모티콘 길이, 클립보드 길이) 의 튜플 형태로 기록하였습니다.

2) 알고리즘

  • 다이나믹 프로그래밍
  • BFS

3) 풀이 코드

사용 언어 - Python

import sys
from collections import deque
sys.stdin = open('input.txt')

S = int(sys.stdin.readline())                   # 목표 이모티콘 길이
visited = {}                                    # 이모티콘, 클립보드 길이별 탐색 여부

q = deque([(1, 0, 0)])                          # 초기 이모티콘 길이 1, 클립보드 0, 연산 시간 0

while q:
    emoticon, clipboard, ans = q.popleft()      # 현재 이모티콘 길이, 클립보드 길이, 연산 시간
    if emoticon == S:                           # 이모티콘 길이가 목표 도달시, 종료
        print(ans)
        break
    elif emoticon <= 0:                         # 이모티콘의 길이 음수가 되려는 경우, 해당 경우 무시
        continue

    ans += 1                                                        # 연산 시간 + 1

    if not visited.get((emoticon, emoticon), False):                # 클립보드에 복사한 경우
        visited[(emoticon, emoticon)] = ans                         # 방문 처리
        q.append((emoticon, emoticon, ans))                         # 큐에 추가

    if not visited.get((emoticon+clipboard, clipboard), False):     # 이모티콘에 붙여넣기 한 경우
        visited[(emoticon+clipboard, clipboard)] = ans
        q.append((emoticon+clipboard, clipboard, ans))
    
    if not visited.get((emoticon-1, clipboard), False):             # 이모티콘 하나 삭제한 경우
        visited[(emoticon-1, clipboard)] = ans
        q.append((emoticon-1, clipboard, ans))

🔗 문제 링크

- https://www.acmicpc.net/problem/14226

 

14226번: 이모티콘

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

www.acmicpc.net

 

 

※ 오류 및 오타, 다른 의견이 있는 경우 댓글을 남겨주시면 감사하겠습니다

댓글