점화식
-
[백준] 14226번 이모티콘 (by Python)Programming/Algorithm 2021. 2. 7. 00:48
문제 처음에는 떠오르는대로 BFS로 풀었지만 코드를 짜는 와중에도 뭔가 문제를 다 파악하지 못한 풀이라는 생각이 들었고, 아니나 다를까 나보다 시간을 90% 정도 절약한 분들은 Dynamic Programming을 통해 푸신 분들이었다. 간결한 코드에 끌려 원리를 고민해봤지만 수학적인 증명은 스스로 해내지 못했다. 고민해보았고, 앞으로도 더 고민해보겠지만 지금은 더 다양한 테스트 케이스에서 해당 원리가 적용된다는 확신이 없으므로 이런 유형의 문제를 만났을 때는 확실한 풀이를 먼저 시도해볼 것 같다. 좀 느릴지라도, 스스로 납득되는 코드를 짜고 싶다. 첫 번째 풀이 (by BFS) from collections import deque s = int(input()) q = deque() next_q = de..