백준_14226_이모티콘

구글링한 내용

• 나는 1차원 visited배열의 index로 스티커갯수를 두고, value로는 걸린 시간을 할당해서 계산했다.
• 하지만 bfs방식으로 뻗어나가면서 바뀌는, 끌고가는 인자는 → 화면에 나타나는 스티커갯수, 현재 clip보드의 스티커 갯수, 걸린 시간 ⇒ 총 3가지다
  
• 그래서 2차원 배열과 그에 따른 값으로 3개를 나타낼 수도 있겠지만, 구글링에서는 딕셔너리를 활용해서 값의 존재여부를 확인 후 3가지 연산을 실행하는 방식을 했음.

👉 단순히 걸리는 “시간”을 카운트하는거에 집중해서 1차원 배열까지만 생각했다. 변화하는 인자값이 여러 개면 2차원, 딕셔너리까지 사고를 확장해보자

Comment

• 그래도 현재 스티커 갯수와 클립보드의 갯수를 동시에 관리하고자 queue에서 관리할 생각 + BFS사고로 문제에 임했다

⚠️ Error

• 복사 + 붙여넣기를 한 세트로 생각해서 한번에 시간을 +2 해서 계산하다가 틀렸음 복사만 하고 넘어가는 경우가 있어서 문제가 됐음
  
• 문제에서 복사 - 붙여넣기를 한 세트로 붙이지 않았음! 할 수 있는 연산이 3개 → 3개의 가지를 모두 뻗기! 경우의 수를 내 머릿속 생각으로 단정짓지 말기…! ⇒ 현재 화면에 있는 스티커 갯수가 목표값보다 적을 때만 1개 삭제하는 연산을 실행하는게 문제였음

---

• 풀기 전 문제 이해를 위해 메모해보기

  # 2초 / 512MB 
  
  # 총 S개 보내기
  # 이미 화면에 1개 입력 
  # 3가지 연산만 사용 -> S개 만들기 
  
  # 연산
  # 화면에 있는거, 모두 복사 -> 클립보드 저장
      # 이전 내용은 덮어쓰기 
  
  # 클립보드에 모든 임티 -> 화면에 붙여넣기
      # 클립보드 비어있으면 붙여넣기 불가 
  
  # 화면에 있는 것중 하나 삭제 
  
  # 모든 연산은 1초 
  
  # Input
  # S : 2이상, 1000이하 
  
  # Output
  # 이모티콘 S개를 만들기 위한 시간의 최솟값

• 🥳 구글링 참고한 정답 🥳

  from collections import deque
  
  S = int(input())
  visited = [[-1] * (2002) for _ in range(2002)]
  def bfs(n):
      # init queue & visited
      queue = deque()
      visited[n][0] = 0
      queue.append((n, 0))
  
      while queue:
          # pop
          cur, cur_clip = queue.popleft()
  
          # terminal condition 
          if cur == S:
              print(visited[cur][cur_clip])
              break 
  
       	# 경계 검사 
          if cur -1 >= 0:
              # 줄이는 연산
              if visited[cur-1][cur_clip] == -1:
                  visited[cur-1][cur_clip] = visited[cur][cur_clip] + 1
                  queue.append((cur-1, cur_clip))
                  
          # 클립보드에 복사 연산 
          if visited[cur][cur] == -1:
              visited[cur][cur] = visited[cur][cur_clip] + 1
              queue.append((cur, cur))
  
          # 경계검사 & 화면에 붙여넣기 연산 
          if cur + cur_clip <= S and visited[cur + cur_clip][cur_clip] == -1:
              visited[cur + cur_clip][cur_clip] = visited[cur][cur_clip] + 1
              queue.append((cur + cur_clip, cur_clip))
  bfs(1)

• 틀린코드

  from collections import deque
  
  S = int(input())
  
  def bfs(n):
      # init queue & visited
      # clip 데이터 값
      clip = 1
      queue = deque()
      queue.append((n, clip))
      visited[n] = 2
  
      # while
      while queue:
          # pop
          cur, cur_clip = queue.popleft()
          # terminal condition 
          if cur == S:
              break 
  
          # if 목표갯수보다 많으면
          if cur > S :
              # 줄이는 연산
              if visited[cur-1] == -1:
                  visited[cur-1] = visited[cur] + 1
                  queue.append((cur-1, cur_clip))
          # 아직 모자르면
          else:
              # 현재 clip값을 더하는 자리가 0이 아니라면 == 아직 방문 전이라면
              if visited[cur + cur_clip] == -1:
                  # 기존 clip값을 복사만 하므로, + 1
                  visited[cur + cur_clip] = visited[cur] + 1
                  queue.append((cur + cur_clip, cur_clip))
              
              # 화면에 있는거 모두 복사 & 클립보드 저장 : + 2초
              if visited[cur*2] == -1:
                  visited[cur*2] = visited[cur] + 2 
                  queue.append((cur*2, cur))
  
  # 시작 이모티콘
  visited = [-1] * (2002)
  bfs(2)
  print(visited[S])

• 참고 블로그 [백준 14226번] 이모티콘 - 파이썬