10164번: 격자상의 경로 www.acmicpc.net 이 문제는 N*M의 격자에서 맨 왼쪽 위 칸에서 출발해 맨 오른쪽 아래 칸까지 가는 서로 다른 경로의 수를 구하는 문제이나 중간에 반드시 경유해야 하는 칸이 주어질 수도 있다. 이를 해결하기 위해서는 각 칸에 대해 그 칸까지 도달하기 위한 경로의 수를 저장하는 배열을 만든다. 그리고 맨 왼쪽 위 칸부터 시작해 각 칸마다 경로의 수를 순차적으로 구하는데, 임의의 칸까지 도달하기 위한 경로의 수는 그 칸의 바로 위 칸까지 가기 위한 경로의 수와 바로 왼쪽 칸까지 가기 위한 경로의 수를 더해서 구한다. 왜냐하면 이동 방향이 항상 오른쪽 또는 아래쪽이기 때문이다. 이때 만약 반드시 경유해야 하는 칸이 있을 경우, 첫 칸에서 시작해 경유해야 하는 칸까지 가..
