백준 14266 파이썬

 

14226번: 이모티콘

풀이

1. 문제에서 필요한 데이터: 현재 화면에 있는 이모티콘 개수, 클립보드에 있는 이모티콘 개수, 현재까지 걸린 시간 3가지가 필요

2. 3가지를 표현할 방법: 2차원 배열 => { d[스크린에 있는 이모티콘개수][클리보드에 있는 이모티콘 개수] } => 걸린 시간

3. 주의사항: 인덱스로 개수를 표현하고 있기 때문에 배열의 인덱스가 제한 범위를 벗어나지 않도록 해야한다. ex) 1000까지 이므로 1000을 넘어가지 않도록, 삭제할 시 음수 인덱스가 나오지 않도록. + 처음 2차원 배열을 할당할 때 n + 1로 메모리할당.

처음에는 메모리 초과가 나왔다. 그래서 최소한의 메모리로 3개의 데이터를 표현할 방법이 없을까.. 하다 2차원 배열을 이용할 수 있었다.

런타임 에러로, index 에러가 나왔는데, 그 이유는 이모티콘 제거시, 음수의 인덱스가 나올 수 있고, 이를 제외하고 1000을 넘는 인덱스도 나올 수 있기 때문에 제한이 필요했다.

코드

from collections import deque


n = int(input())
d = [[-1] * (n+1) for _ in range(n+1)] # 인덱스 자체를 개수로 표현하므로 n + 1

def sol():
    q = deque([(1,0)])
    d[1][0] = 0
    while q:
        s, c = q.popleft()
        if s == n:
            print(d[s][c])
            exit()
        if s <= n and d[s][s] == -1: # 1000개 이하의 인덱스여야함.
            d[s][s] = d[s][c] + 1
            q.append((s, s))
        if s+c <= n and d[s+c][c] == -1: # 1000개 이하의 인덱스여야함.
            d[s+c][c] = d[s][c] + 1
            q.append((s + c, c))
        if s - 1 >=0 and d[s-1][c] == -1: # 음수가 아닌 인덱스여야함.
            d[s-1][c] = d[s][c] + 1
            q.append((s-1, c))
sol()
# 리스트의 인덱스 값을 가지고 연산을 한다면, 그 값이 제한 범위를 벗어나는지도 확인해야하고, 그 값 자체가
# 개수를 나타낸다면, 0부터가 인덱스이므로 n+1 로 할당하는 것을 잊지말자.

 

참고

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