수다닷컴

아래의 알고리즘을 C++로 구현해야하는데요..

어떤 알고리즘을 사용해야할까요?
알고리즘만 안다면 코딩은 제가 직접 할 수 있습니다....

메뚜기 게임
메뚜기 게임은 체스판의 맨왼쪽 위 칸에 놓인 메뚜기 로봇을 오른쪽이나 아래쪽으로 뛰어 이동하기를 반복하여 맨오른쪽 아래 칸으로 이동시키는 게임이다. 이 게임에서 뛰는 횟수가 적은 사람이 이긴다. 게임중에 메뚜기 로봇이 체스판 밖으로 나갈 수는 없다. 체스판의 각 칸에는 두 값 R과 D가 주어져 있는데, R은 한번에 오른쪽으로 뛸 수 있는 칸의 수를, D는 아래쪽으로 뛸 수 있는 칸의 수를 나타낸다.
예를 들어 아래 그림과 같이 체스판이 주어져 있다고 하자. 그림에서 행의 수는 3이고 위에서 아래로 행 번호가 1부터 3까지 붙어 있다고 가정한다. 열의 수는 4이고 열 번호는 왼쪽에서 오른쪽으로 1부터 4까지 붙어 있다. 각 칸에 있는 숫자는 (R, D) 쌍이다. 맨처음 칸 1행 1열에 놓인 메뚜기 로봇은 R값이 1이므로 오른쪽으로는 1칸만 뛸 수 있고, D값이 2이므로 아래쪽으로는 1칸이나 2칸을 뛸 수 있다.

(1,2)
(1,2)
(1,2)
(2,1)
(3,1)
(1,1)
(1,2)
(1,2)
(1,1)
(1,1)
(1,2)
(2,2)

맨오른쪽 아래칸으로 이동할 수 있는 방법으로 우선 오른쪽으로 1칸, 아래쪽으로 2칸, 오른쪽을 1칸, 다시 오른쪽으로 1칸 뛰어 가는 방법이 있다. 이때 총 뛴 횟수는 4회이다. 다른 방법으로는 아래쪽으로 1칸, 오른쪽으로 3칸, 아래쪽으로 1칸을 뛰어 목적지까지 갈 수가 있으며, 이때는 총 뛴 횟수는 3회이다. 2회 뛰어서 목적지까지 갈 수 있는 방법이 없으므로 3회가 최소값이 된다.

문제는 체스판과 체스판의 각 칸에 R, D값이 주어질 때, 맨왼쪽 위칸에 있는 메뚜기 로봇이 맨오른쪽 아래칸까지 이동프?이동하기 위하여 뛰어야 하는 최소 횟수를 구하는 프로그램을 작성하는 것이다. 프로그램 이름은 hopper.cpp(c), 설명 파일 이름은 hopper.doc(hwp)로 하고 프로그램의 실행시간은 1초를 초과할 수 없다. 부분 점수는 없다.

입력 형식
입력 파일의 이름은 input.txt이다. 첫째 줄에 두 정수 Y와 X가 공백을 사이에 두고 주어진다. 여기서 Y은 체스판의 행의 개수이고 X는 열의 개수이다. 이어서 Y개의 줄이 주어진다. 처음 개의 줄은 체스판 각 칸의 R값이 한 줄에 한 행씩 1행부터 차례로 주어진다. 이어서 Y개의 줄에 체스판 각 칸의 D값이 한 줄에 한 행씩 1행부터 차례로 주어진다. X, Y, R, D는 모두 250 이하인 양의 정수이다.
출력 형식
출력 파일의 이름은 output.txt이다. 첫 줄에 출발지에서 목적지까지 이동하기 위하여 메뚜기 로봇이 뛰어야 하는 최소 횟수를 출력한다.

입력과 출력의 예
입력(input.txt)
3 4
1 1 1 2
3 1 1 1
1 1 1 2
2 2 2 1
1 1 2 2
1 1 2 2
출력(output.txt)
3

신청하기