-
[백준] 14226번 문제 (이모티콘) 파이썬(Python) 풀이Problem Solving/Baekjoon 2021. 10. 14. 14:05
https://www.acmicpc.net/problem/14226
from collections import deque s = int(input()) v = [[False] * (s + 1) for _ in range(s + 1)] q = deque() q.append([1, 0, 0]) v[1][0] = True while q: screen, clipboard, count = q.popleft() if screen == s: print(count) break if screen != clipboard and not v[screen][screen]: v[screen][screen] = True q.append([screen, screen, count + 1]) if screen + clipboard <= s and clipboard != 0 and not v[screen + clipboard][clipboard]: v[screen + clipboard][clipboard] = True q.append([screen + clipboard, clipboard, count + 1]) if screen != 0 and not v[screen - 1][clipboard]: v[screen - 1][clipboard] = True q.append([screen - 1, clipboard, count + 1])
bfs와 dp가 한 주먹 섞인 문제다.
bfs로 문제에서 주어진 모든 경우의 수를 구하되,
앞서 연산을 했던 경우의 수를 또 다시 구하는 경우를 피해야 된다.
그러기 위해서는 v 라는 2차원 배열로 (v[screen][clipboard]) 연산을 할 때마다,
해당 경우를 v에 기록해 중복된 계산을 안 하면 된다.
'Problem Solving > Baekjoon' 카테고리의 다른 글
[백준] 1149번 문제 (RGB거리) 파이썬(Python) 풀이 (0) 2021.12.27 [백준] 13549번 문제 (숨바꼭질 3) 파이썬(Python) 풀이 (0) 2021.10.14 [백준] 13913번 문제 (숨바꼭질 4) 파이썬(Python) 풀이 (0) 2021.10.14 [백준] 12851번 문제 (숨바꼭질 2) 파이썬(Python) 풀이 (0) 2021.10.14 [백준] 1743번 문제 (음식물 피하기) 파이썬(Python) 풀이 (0) 2021.10.14