📖 문제
🧑🏻💻 풀이 과정
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
※ 오류 및 오타, 다른 의견이 있는 경우 댓글을 남겨주시면 감사하겠습니다
'알고리즘 문제풀이 > Python' 카테고리의 다른 글
[백준] 10217 KCM Travel (0) | 2022.07.15 |
---|---|
[백준] 6549 히스토그램에서 가장 큰 직사각형 (0) | 2022.07.14 |
[백준] 17135 캐슬 디펜스 (0) | 2022.07.12 |
[백준] 17143 낚시왕 (0) | 2022.07.11 |
[백준] 15684 사다리 조작 (0) | 2022.07.10 |
댓글