[백준 14226] 이모티콘 (Python)

www.acmicpc.net/problem/14226

14226번: 이모티콘

문제풀이

S : 입력값

dp : 화면과 클립보드를 표현할 2차원 리스트, dp[i][j] = x : 화면에 있는 이모티콘의 갯수 i개, 클립보드에 있는 이모티콘의 갯수j개 일때 걸린 시간 x초

q : i, j 를 BFS로 탐색하는 deque

ans : 결과값

 

1. BFS를 이용해 세 가지 경우를 탐색하여 deque에 넣어준다. (이때 각 연산은 1초가 소요)

 

- 화면에 있는 i개의 이모티콘을 클립보드에 붙이는 경우 => dp[i][i] = dp[i][j] + 1

문제에서 클립보드에 이모티콘을 붙일 경우 덮어씌워진다고 하였기 때문에 클립보드도 i개의 이모티콘이 된다.

 

- 클립보드에 있는 j개의 이모티콘을 화면에 붙이는 경우 => dp[i+j][j] = dp[i][j] + 1

 

- 화면에서 이모티콘을 1개 삭제하는 경우 => dp[i - 1]j] = dp[i][j] + 1

 

2. 화면에 있는 이모티콘의 갯수가 S개 일때까지 deque에 (i, j)를 넣어주면서 1의 과정 반복

 

3. 화면에 있는 이모티콘의 갯수가 S개 일때 dp[S] 에서 최소값을 결과로 출력(-1은 초기값이므로 제외)

 

 

코드

import sys
from collections import deque

if __name__ == '__main__':
    S = int(input())

    # dp[i][j] = x : 화면에 있는 이모티콘의 갯수 i개, 클립보드에 있는 이모티콘의 갯수 j개 일때 걸린 시간 x초
    dp = [[-1] * 1001 for _ in range(1001)]
    dp[1][0] = 0
    q = deque([(1, 0)])
    # 각 연산은 1초가 소요
    while q:
        i, j = q.popleft()
        # 화면에 있는 i개의 이모티콘을 클립보드에 붙이는 경우
        if i <= 1000:
            if dp[i][i] == -1:
                dp[i][i] = dp[i][j] + 1
                q.append((i, i))
        # 클립보드에 있는 j개의 이모티콘을 화면에 붙이는 경우
        if i + j <= 1000:
            if dp[i + j][j] == -1:
                dp[i + j][j] = dp[i][j] + 1
                q.append((i + j, j))
        # 화면에서 이모티콘을 1개 삭제하는 경우
        if i - 1 >= 0:
            if dp[i - 1][j] == -1:
                dp[i - 1][j] = dp[i][j] + 1
                q.append((i - 1, j))
        if i == S: break
    ans = sys.maxsize
    for y in dp[S]:
        if y != -1: ans = min(ans, y)
    print(ans)

 

결과

 

문제풀이나 코드에서 이상한 부분 지적은 언제나 환영합니다!