[C/C++] 백준 #1890 점프(동적 계획법)
이번 문제는 동적 계획법을 이용해서 풀었습니다. 사실 동적 계획법이 아니라 너비 우선 탐색(BFS)를 사용해도 같은 결과를 얻을 수 있습니다. 그렇지만 단순 반복문을 사용할 수 있는 동적 계획법에 비해서 효율이 떨어지게 되겠죠. 동적 계획법 알고리즘은 간단합니다. \(d_{i, j} \)를 시작점에서 \((i, j)\)로 가는 경로의 개수라고 한다면, 1. NxN 공간을 0으로 초기화합니다. \( d_{i, j} = 0 \) 2. 시작점을 1로 놓습니다. 즉, 시작점에서 시작점으로 가는 경로는 한가지입니다. \(d_{0, 0} = 1\) 3. 시작점에서부터 오른쪽 방향 우선으로, 아래로 이동하면서 갈 수 있는 모든 곳 \(d_{i+a_{i, j}, j}\) 값과 \(d_{i, j+a_{i, j}}\) 값..
2022. 11. 1.
