[백준] boj-14226 이모티콘 파이썬

Yewon Choi·2021년 1월 28일
0

알고리즘

목록 보기
6/11

[ 문제 ]

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

[ 알고리즘 유형 ]

다이나믹 프로그래밍
그래프 이론
그래프 탐색
너비 우선 탐색

[ 정답 코드 ]

from collections import deque
n = int(input())
dist = [[-1]* (n+1) for _ in range(n+1)]
q = deque()
q.append((1,0))  # 화면 이모티콘 개수, 클립보드 이모티콘 개수
dist[1][0] = 0
while q:
    s,c = q.popleft()
    if dist[s][s] == -1: # 방문하지 않았으면
        dist[s][s] = dist[s][c] + 1
        q.append((s,s))
    if s+c <= n and dist[s+c][c] == -1:
        dist[s+c][c] = dist[s][c] + 1
        q.append((s+c, c))
    if s-1 >= 0 and dist[s-1][c] == -1:
        dist[s-1][c] = dist[s][c] + 1
        q.append((s-1, c))
answer = -1
for i in range(n+1):
    if dist[n][i] != -1:
        if answer == -1 or answer > dist[n][i]:
            answer = dist[n][i]
print(answer)

[ 풀이 방법 ]

걸리는 시간의 최솟값을 구한다. 즉, 최단시간을 구해야하니 BFS로 풀면 된다.

3가지 연산만 사용해서 이모티콘을 S개 만든다
즉, 화면에 이모티콘의 개수 s와 클립보드에 있는 이모티콘의 개수c를 고려해서 풀면 된다.

  1. 화면에 있는 이모티콘을 모두 복사해서 클립보드에 저장한다.
    복사 : (s,c) -> (s,s)
  2. 클립보드에 있는 모든 이모티콘을 화면에 붙여넣기 한다.
    붙여넣기 : (s,s) -> (s+c, c)
  3. 화면에 있는 이모티콘 중 하나를 삭제한다.
    (s,s) -> (s-1, c)
    => 모든 연산은 1초가 걸리니 모든 경로의 가중치는 1이다.
    따라서, dist[s][c] + 1 과 같이 1을 더해줘야 한다.
profile
https://github.com/devAon 찰나의 개발흔적을 남기는 개발블로그 입니다 🐥 https://aonee.tistory.com 에서 Velog로 블로그 이전 작업중입니다 ! 🎶

1개의 댓글

comment-user-thumbnail
2022년 5월 7일

풀이방법 2번, 3번에 (s,s) => (s,c) 오타가 있는 것 같습니다.
덕분에 문제 잘 해결합니다. 감사합니다.

답글 달기