[백준] 14226 이모티콘

📖 문제

---

🧑🏻‍💻 풀이 과정

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번: 이모티콘

 

 

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