[C/C++] 백준 #2096 내려가기(동적 계획법)
내려가기 문제는 간단한 형태의 동적 계획법(Dynamic Programming)을 사용하면 됩니다. 동적 계획법을 사용하지 않고, DFS나 BFS를 이용해서 풀 수는 있지만, 그렇게 하면 시간이 많이 걸립니다. 다익스트라 알고리즘을 사용해도 동적 계획법을 적용한 것과 같은 효과를 낼 수 있습니다. https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 처음에는 설명을 이해하기 어려웠습니다. 주어진 N이 주어지면, 3xN 형태의 공간이 발생합니다. 맨 위층에서는 3칸..
2023. 3. 30.