분할 정복을 이용한 최적화1 [백준 13261] 탈옥 (분할 정복을 사용한 최적화) (Platinum I) 분할 정복을 사용한 최적화 입문 문제인 탈옥이다. 분할 정복을 사용한 최적화는 한 번 읽어서는 도무지 어떤 방식으로 코드를 짜야 할지 감이 오지 않는다(적어도 나에게는 그랬다). 나에게 있어서 이해를 방해하는 가장 큰 사실은 분할 정복과 DP가 도저히 어울리지 않는 것 같다는 사실이었다. 예컨대 피보나치 DP 문제를 살펴보자. 1 -> 1 -> 2 -> 3 -> 5 -> 8 -> 13 -> 21 -> ... 이렇게 한 칸을 계산하는 일이 다음 칸의 계산에 영향을 미친다. 이 DP 문제를 억지로라도 분할 정복으로 계산할 수 있을까? 힘들어 보인다. 애초에 문제의 분할 자체를 어떻게 정의해야 할지도 모르겠다. 일단 탈옥 문제의 DP 식은 다음과 같다. i명의 간수를 사용해서 j번째 감옥까지 감시를 한다면, .. 2023. 6. 11. 이전 1 다음
