이모티콘 [백준 14226] - python

 

from collections import deque
import sys
input = sys.stdin.readline

def BOJ14226() :
  S = int(input().strip())
  graph = [[-1 for _ in range(S+1)] for _ in range(S+1)]  # 개수 별 최소 시간
  graph[1][0] = 0
  
  def bfs() :
    queue = deque()
    queue.append([1, 0])

    while queue :
      curr_node, curr_clip  = queue.popleft()

      # 클립 보드에 현재 화면에 있는 것을 넣는 과정
      if graph[curr_node][curr_node] == -1 :
        graph[curr_node][curr_node] = graph[curr_node][curr_clip] + 1
        queue.append([curr_node, curr_node])
      
      # 클립보드에서 가져와서 화면에 그리는 과정
      next_node = curr_node + curr_clip
      if 0 < next_node <= S and graph[next_node][curr_clip] == -1 :
        graph[next_node][curr_clip] = graph[curr_node][curr_clip] + 1
        queue.append([next_node, curr_clip])
      
      # 화면에 있는 이모티콘 중 하나를 삭제하는 과정
      next_node = curr_node - 1
      if 0 < next_node <= S and graph[next_node][curr_clip] == -1 :
        graph[next_node][curr_clip] = graph[curr_node][curr_clip] + 1
        queue.append([next_node, curr_clip])

  bfs()
  result = -1
  for i in range(S+1) :
    if graph[S][i] != -1 :
      if result == -1 :
        result = graph[S][i]
        continue
      result = min(result, graph[S][i])

  print(result)

BOJ14226()

 

문제 풀이 접근 방법:

1. 문제에 대한 이해가 잘 되지 않았던 것 같습니다. 예시 입력에 관한 실제로 탐색을 진행해 봤고 감을 잡을 수 있었습니다.

• 3가지 동작중 하나를 수행, 동작 하나에 1초를 소요
  1. 화면의 모두를 복사해서 클립 보드에 저장
  2. 클립 보드에 있는 모든 이모티콘을 화면에 붙여넣기
  3. 화면에 있는 이모티콘 중 하나를 삭제
• 2개 => 2초
  1 -> 저장(1) -> 복사 2
  4개 => 4초
  1 -> 저장(1) -> 복사 2 -> 저장(2) -> 복사 4
  6개 => 5초
  1 -> 저장(1) -> 복사 2 -> 저장(2) -> 복사 4 -> 복사 6
  18개 => 8초
  1 -> 저장(1) -> 복사 2 -> 저장(2) -> 복사 4 -> 복사 6 -> 저장(6) -> 복사 12 -> 복사 18

2. 개수를 만들 었을때 클립 보드의 값이 여러개가 될 수 있지 않을까 라고 생각을 하였습니다. 
ex) 10개를 만드는데 [현재 개수, 클립보드]로 나타낼 수 있을때 [11, 10]개에서 1개씩 빼거나 [5, 5]개 에서 복사를 하는 경우가 있을 수 있습니다. 이렇게 되면 
[10, 1], [10, 5] 의 두가지 경우가 생기게 됩니다. 
그래서 이차원 배열의 사용을 생각하게 되었습니다.

또한 이차원 배열일 경우 배열의 크기만 1000000 * 4 byte가 되므로 메모리의 여유가 적다고 판단하여 입력 으로 받은 값 까지만 이차원 배열의 범위를 결정하였습니다.

S = int(input().strip())
graph = [[-1 for _ in range(S+1)] for _ in range(S+1)]  # 개수 별 최소 시간
graph[1][0] = 0

 

3. bfs

3개의 경우가 있을 수 있습니다.

1. 클립 보드에 현재 화면에 있는 것을 넣는 과정
2. 클립 보드에서 가져와서 화면에 그리는 과정
3. 화면에 있는 이모티콘 중 하나를 삭제하는 과정

3개의 경우 모두 1초씩 소요가 됩니다.

그래서 bfs내에서 다음과 같이 구성 후 이차원 배열을 채움 + queue에 추가를 진행합니다.

# 클립 보드에 현재 화면에 있는 것을 넣는 과정
if graph[curr_node][curr_node] == -1 :
  graph[curr_node][curr_node] = graph[curr_node][curr_clip] + 1
  queue.append([curr_node, curr_node])

# 클립보드에서 가져와서 화면에 그리는 과정
next_node = curr_node + curr_clip
if 0 < next_node <= S and graph[next_node][curr_clip] == -1 :
  graph[next_node][curr_clip] = graph[curr_node][curr_clip] + 1
  queue.append([next_node, curr_clip])

# 화면에 있는 이모티콘 중 하나를 삭제하는 과정
next_node = curr_node - 1
if 0 < next_node <= S and graph[next_node][curr_clip] == -1 :
  graph[next_node][curr_clip] = graph[curr_node][curr_clip] + 1
  queue.append([next_node, curr_clip]

 

4. 모든 탐색을 끝내고 해당 개수에서 최솟값을 출력해 줍니다.

result = -1
for i in range(S+1) :
  if graph[S][i] != -1 :
    if result == -1 :
      result = graph[S][i]
      continue
    result = min(result, graph[S][i])

print(result)