10164
-
백준 10164번 격자상의 경로 [DP] :: 마이구미알고리즘 풀이/동적계획법 2017. 3. 5. 23:59
이번 글은 백준 알고리즘 문제 10164번 "격자상의 경로" 를 다뤄본다.동적계획법으로 접근하는 문제이다.일단 문제를 보자. 격자의 1번 칸에서 출발한 어떤 로봇이 아래의 두 조건을 만족하면서 N×M번 칸으로 가고자 한다. 조건 1: 로봇은 한 번에 오른쪽에 인접한 칸 또는 아래에 인접한 칸으로만 이동할 수 있다. (즉, 대각선 방향으로는 이동할 수 없다.)조건 2: 격자에 ○로 표시된 칸이 있는 경우엔 로봇은 그 칸을 반드시 지나가야 한다. 동그라미 표시된 칸을 무조건 지나가는 경로의 수를 찾는 문제이다.점화식을 만드는 방법은 문제에서 알려준 조건을 보면 쉽게 파악할 수 있다. 조건 1을 보면, 오른쪽에 인접한 칸 또는 아래에 인접한 칸으로만 이동할 수 있다고 한다.기준이 되는 칸으로 올 수 있는 경우..