백준 온라인 저지, 다이나믹프로그래밍 / 1890번: 점프 (파이썬)

문제

N×N 게임판에 수가 적혀져 있다. 이 게임의 목표는 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 점프를 해서 가는 것이다.

각 칸에 적혀있는 수는 현재 칸에서 갈 수 있는 거리를 의미한다. 반드시 오른쪽이나 아래쪽으로만 이동해야 한다. 0은 더 이상 진행을 막는 종착점이며, 항상 현재 칸에 적혀있는 수만큼 오른쪽이나 아래로 가야 한다. 한 번 점프를 할 때, 방향을 바꾸면 안 된다. 즉, 한 칸에서 오른쪽으로 점프를 하거나, 아래로 점프를 하는 두 경우만 존재한다.

가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 이동할 수 있는 경로의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 오른쪽 아래 칸에는 항상 0이 주어진다.

출력

가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 문제의 규칙에 맞게 갈 수 있는 경로의 개수를 출력한다. 경로의 개수는 2⁶³-1보다 작거나 같다.

제한

 

예제 입력 1

4 2 3 3 1 1 2 1 3 1 2 3 1 3 1 1 0 

예제 출력 1

3 

힌트

그림 1	그림 2

W3sicHJvYmxlbV9pZCI6IjE4OTAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM4MTBcdWQ1MDQiLCJkZXNjcmlwdGlvbiI6IjxwPk4mdGltZXM7TiBcdWFjOGNcdWM3ODRcdWQzMTBcdWM1ZDAgXHVjMjE4XHVhYzAwIFx1YzgwMVx1ZDYwMFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1Yzc3NCBcdWFjOGNcdWM3ODRcdWM3NTggXHViYWE5XHVkNDVjXHViMjk0IFx1YWMwMFx1YzdhNSBcdWM2N2NcdWNhYmQgXHVjNzA0IFx1Y2U3OFx1YzVkMFx1YzExYyBcdWFjMDBcdWM3YTUgXHVjNjI0XHViOTc4XHVjYWJkIFx1YzU0NFx1Yjc5OCBcdWNlNzhcdWM3M2NcdWI4NWMgXHVhZGRjXHVjZTU5XHVjNWQwIFx1YjlkZVx1YWM4YyBcdWM4MTBcdWQ1MDRcdWI5N2MgXHVkNTc0XHVjMTFjIFx1YWMwMFx1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMwMSBcdWNlNzhcdWM1ZDAgXHVjODAxXHVkNjAwXHVjNzg4XHViMjk0IFx1YzIxOFx1YjI5NCBcdWQ2MDRcdWM3YWMgXHVjZTc4XHVjNWQwXHVjMTFjIFx1YWMwOCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YWM3MFx1YjlhY1x1Yjk3YyBcdWM3NThcdWJiZjhcdWQ1NWNcdWIyZTQuIFx1YmMxOFx1YjRkY1x1YzJkYyBcdWM2MjRcdWI5NzhcdWNhYmRcdWM3NzRcdWIwOTggXHVjNTQ0XHViNzk4XHVjYWJkXHVjNzNjXHViODVjXHViOWNjIFx1Yzc3NFx1YjNkOVx1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQuIDBcdWM3NDAgXHViMzU0IFx1Yzc3NFx1YzBjMSBcdWM5YzRcdWQ1ODlcdWM3NDQgXHViOWM5XHViMjk0IFx1Yzg4NVx1Y2MyOVx1YzgxMFx1Yzc3NFx1YmE3MCwgXHVkNTZkXHVjMGMxIFx1ZDYwNFx1YzdhYyBcdWNlNzhcdWM1ZDAgXHVjODAxXHVkNjAwXHVjNzg4XHViMjk0IFx1YzIxOFx1YjljY1x1ZDA3YyBcdWM2MjRcdWI5NzhcdWNhYmRcdWM3NzRcdWIwOTggXHVjNTQ0XHViNzk4XHViODVjIFx1YWMwMFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1ZDU1YyBcdWJjODggXHVjODEwXHVkNTA0XHViOTdjIFx1ZDU2MCBcdWI1NGMsIFx1YmMyOVx1ZDVhNVx1Yzc0NCBcdWJjMTRcdWFmYjhcdWJhNzQgXHVjNTQ4IFx1YjQxY1x1YjJlNC4gXHVjOTg5LCBcdWQ1NWMgXHVjZTc4XHVjNWQwXHVjMTFjIFx1YzYyNFx1Yjk3OFx1Y2FiZFx1YzczY1x1Yjg1YyBcdWM4MTBcdWQ1MDRcdWI5N2MgXHVkNTU4XHVhYzcwXHViMDk4LCBcdWM1NDRcdWI3OThcdWI4NWMgXHVjODEwXHVkNTA0XHViOTdjIFx1ZDU1OFx1YjI5NCBcdWI0NTAgXHVhY2JkXHVjNmIwXHViOWNjIFx1Yzg3NFx1YzdhY1x1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhYzAwXHVjN2E1IFx1YzY3Y1x1Y2FiZCBcdWM3MDQgXHVjZTc4XHVjNWQwXHVjMTFjIFx1YWMwMFx1YzdhNSBcdWM2MjRcdWI5NzhcdWNhYmQgXHVjNTQ0XHViNzk4IFx1Y2U3OFx1YzczY1x1Yjg1YyBcdWFkZGNcdWNlNTlcdWM1ZDAgXHViOWRlXHVhYzhjIFx1Yzc3NFx1YjNkOVx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YWNiZFx1Yjg1Y1x1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YWM4Y1x1Yzc4NCBcdWQzMTBcdWM3NTggXHVkMDZjXHVhZTMwIE4gKDQgJmxlOyBOICZsZTsgMTAwKVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWRmOCBcdWIyZTRcdWM3NGMgTlx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhYzAxIFx1Y2U3OFx1YzVkMCBcdWM4MDFcdWQ2MDBcdWM4MzggXHVjNzg4XHViMjk0IFx1YzIxOFx1YWMwMCBOXHVhYzFjXHVjNTI5IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjZTc4XHVjNWQwIFx1YzgwMVx1ZDYwMFx1Yzc4OFx1YjI5NCBcdWMyMThcdWIyOTQgMFx1YmNmNFx1YjJlNCBcdWQwNmNcdWFjNzBcdWIwOTggXHVhYzE5XHVhY2UwLCA5XHViY2Y0XHViMmU0IFx1Yzc5MVx1YWM3MFx1YjA5OCBcdWFjMTlcdWM3NDAgXHVjODE1XHVjMjE4XHVjNzc0XHViYTcwLCBcdWFjMDBcdWM3YTUgXHVjNjI0XHViOTc4XHVjYWJkIFx1YzU0NFx1Yjc5OCBcdWNlNzhcdWM1ZDBcdWIyOTQgXHVkNTZkXHVjMGMxIDBcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMFx1YzdhNSBcdWM2N2NcdWNhYmQgXHVjNzA0IFx1Y2U3OFx1YzVkMFx1YzExYyBcdWFjMDBcdWM3YTUgXHVjNjI0XHViOTc4XHVjYWJkIFx1YzU0NFx1Yjc5OCBcdWNlNzhcdWM3M2NcdWI4NWMgXHViYjM4XHVjODFjXHVjNzU4IFx1YWRkY1x1Y2U1OVx1YzVkMCBcdWI5ZGVcdWFjOGMgXHVhYzA4IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVhY2JkXHViODVjXHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuJm5ic3A7PHNwYW4gc3R5bGU9XCJsaW5lLWhlaWdodDoxLjZlbVwiPlx1YWNiZFx1Yjg1Y1x1Yzc1OCBcdWFjMWNcdWMyMThcdWIyOTQgMjxcL3NwYW4+PHN1cCBzdHlsZT1cImxpbmUtaGVpZ2h0OjEuNmVtXCI+NjM8XC9zdXA+PHNwYW4gc3R5bGU9XCJsaW5lLWhlaWdodDoxLjZlbVwiPi0xXHViY2Y0XHViMmU0IFx1Yzc5MVx1YWM3MFx1YjA5OCBcdWFjMTlcdWIyZTQuPFwvc3Bhbj48XC9wPlxyXG4iLCJoaW50IjoiPHRhYmxlIGNsYXNzPVwidGFibGUgdGFibGUtYm9yZGVyZWQgdGQtY2VudGVyXCI+XHJcblx0PHRib2R5PlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQ+PGltZyBhbHQ9XCJcIiBzcmM9XCJodHRwczpcL1wvdXBsb2FkLmFjbWljcGMubmV0XC81NjNmYmZkYS02NzUwLTQ5Y2EtOTMxZC0xMjVkNDI1OWM4NzBcLy1cL2Nyb3BcLzE5NXgxOTJcLzAsMFwvLVwvcHJldmlld1wvXCIgc3R5bGU9XCJ3aWR0aDogOThweDsgaGVpZ2h0OiA5NnB4O1wiIFwvPjxcL3RkPlxyXG5cdFx0XHQ8dGQ+PGltZyBhbHQ9XCJcIiBzcmM9XCJodHRwczpcL1wvdXBsb2FkLmFjbWljcGMubmV0XC81NjNmYmZkYS02NzUwLTQ5Y2EtOTMxZC0xMjVkNDI1OWM4NzBcLy1cL2Nyb3BcLzY0MHgxOTJcLzMwMiwwXC8tXC9wcmV2aWV3XC9cIiBzdHlsZT1cIndpZHRoOiAzMjBweDsgaGVpZ2h0OiA5NnB4O1wiIFwvPjxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0ZD5cdWFkZjhcdWI5YmMgMTxcL3RkPlxyXG5cdFx0XHQ8dGQ+XHVhZGY4XHViOWJjIDI8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdDxcL3Rib2R5PlxyXG48XC90YWJsZT5cclxuIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIxODkwIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiSnVtcCBUaGUgQm9hcmQhIiwiZGVzY3JpcHRpb24iOiI8cD5BbiBuICZ0aW1lczsgbiBnYW1lIGJvYXJkIGlzIHBvcHVsYXRlZCB3aXRoIGludGVnZXJzLCBvbmUgbm9ubmVnYXRpdmUgaW50ZWdlciBwZXIgc3F1YXJlLiBUaGUgZ29hbCBpcyB0byBqdW1wIGFsb25nIGFueSBsZWdpdGltYXRlIHBhdGggZnJvbSB0aGUgdXBwZXIgbGVmdCBjb3JuZXIgdG8gdGhlIGxvd2VyIHJpZ2h0IGNvcm5lciBvZiB0aGUgYm9hcmQuIFRoZSBpbnRlZ2VyIGluIGFueSBvbmUgc3F1YXJlIGRpY3RhdGVzIGhvdyBsYXJnZSBhIHN0ZXAgYXdheSBmcm9tIHRoYXQgbG9jYXRpb24gbXVzdCBiZS4gSWYgdGhlIHN0ZXAgc2l6ZSB3b3VsZCBhZHZhbmNlIHRyYXZlbCBvZmYgdGhlIGdhbWUgYm9hcmQsIHRoZW4gYSBzdGVwIGluIHRoYXQgcGFydGljdWxhciBkaXJlY3Rpb24gaXMgZm9yYmlkZGVuLiBBbGwgc3RlcHMgbXVzdCBiZSBlaXRoZXIgdG8gdGhlIHJpZ2h0IG9yIHRvd2FyZCB0aGUgYm90dG9tLiBOb3RlIHRoYXQgYSAwIGlzIGEgZGVhZCBlbmQgd2hpY2ggcHJldmVudHMgYW55IGZ1cnRoZXIgcHJvZ3Jlc3MuPFwvcD5cclxuXHJcbjxwPkNvbnNpZGVyIHRoZSA0ICZ0aW1lczsgNCBib2FyZCBzaG93biBpbiBGaWd1cmUgMSwgd2hlcmUgdGhlIHNvbGlkIGNpcmNsZSBpZGVudGlmaWVzIHRoZSBzdGFydCBwb3NpdGlvbiBhbmQgdGhlIGRhc2hlZCBjaXJjbGUgaWRlbnRpZmllcyB0aGUgdGFyZ2V0LiBGaWd1cmUgMiBzaG93cyB0aGUgdGhyZWUgbGVnaXRpbWF0ZSBwYXRocyBmcm9tIHRoZSBzdGFydCB0byB0aGUgdGFyZ2V0LCB3aXRoIHRoZSBpcnJlbGV2YW50IG51bWJlcnMgaW4gZWFjaCByZW1vdmVkLjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2p1bXAoMykucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTQwcHg7IHdpZHRoOjQ5MnB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPllvdXIgdGFzayBpcyB0byB3cml0ZSBhIHByb2dyYW0gdGhhdCBkZXRlcm1pbmVzIHRoZSBudW1iZXIgb2YgbGVnaXRpbWF0ZSBwYXRocyBmcm9tIHRoZSB1cHBlciBsZWZ0IGNvcm5lciB0byB0aGUgbG93ZXIgcmlnaHQgY29ybmVyLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGlucHV0IGNvbnRhaW5zIGEgZmlyc3QgbGluZSB3aXRoIGEgc2luZ2xlIHBvc2l0aXZlIGludGVnZXIgbiwgNCAmbGU7IG4gJmxlOyAxMDAsIHdoaWNoIGlzIHRoZSBudW1iZXIgb2Ygcm93cyBpbiB0aGlzIGJvYXJkLiBUaGlzIGlzIGZvbGxvd2VkIGJ5IG4gcm93cyBvZiBkYXRhLiBFYWNoIHJvdyBjb250YWlucyBuIGludGVnZXJzLCBlYWNoIG9uZSBmcm9tIHRoZSByYW5nZSAwJmhlbGxpcDs5LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBvdXRwdXQgc2hvdWxkIGNvbnNpc3Qgb2YgYSBzaW5nbGUgbGluZSBjb250YWluaW5nIGEgc2luZ2xlIGludGVnZXIsIHdoaWNoIGlzIHRoZSBudW1iZXIgb2YgbGVnaXRpbWF0ZSBwYXRocyBmcm9tIHRoZSB1cHBlciBsZWZ0IGNvcm5lciB0byB0aGUgbG93ZXIgcmlnaHQgY29ybmVyLjxcL3A+XHJcbiIsImhpbnQiOiI8dGFibGUgY2xhc3M9XCJ0YWJsZSB0YWJsZS1ib3JkZXJlZCB0ZC1jZW50ZXJcIj5cclxuXHQ8dGJvZHk+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0ZD48aW1nIGFsdD1cIlwiIHNyYz1cImh0dHBzOlwvXC91cGxvYWQuYWNtaWNwYy5uZXRcLzU2M2ZiZmRhLTY3NTAtNDljYS05MzFkLTEyNWQ0MjU5Yzg3MFwvLVwvY3JvcFwvMTk1eDE5MlwvMCwwXC8tXC9wcmV2aWV3XC9cIiBzdHlsZT1cIndpZHRoOiA5OHB4OyBoZWlnaHQ6IDk2cHg7XCIgXC8+PFwvdGQ+XHJcblx0XHRcdDx0ZD48aW1nIGFsdD1cIlwiIHNyYz1cImh0dHBzOlwvXC91cGxvYWQuYWNtaWNwYy5uZXRcLzU2M2ZiZmRhLTY3NTAtNDljYS05MzFkLTEyNWQ0MjU5Yzg3MFwvLVwvY3JvcFwvNjQweDE5MlwvMzAyLDBcLy1cL3ByZXZpZXdcL1wiIHN0eWxlPVwid2lkdGg6IDMyMHB4OyBoZWlnaHQ6IDk2cHg7XCIgXC8+PFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRkPkZpZ3VyZSAxPFwvdGQ+XHJcblx0XHRcdDx0ZD5GaWd1cmUgMjxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0PFwvdGJvZHk+XHJcbjxcL3RhYmxlPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

접근 방법

- 가장 왼쪽 위 쪽에 위치한 수부터 시작해서 이동 가능한 범위에 있는 dp 테이블에 경우의 수를 입력한다.

코드

# https://www.acmicpc.net/problem/1890
# 접근방법
# 가장 왼쪽 위 쪽에 위치한 수부터 시작해서 이동 가능한 범위에 있는 dp 테이블에 경우의 수를 입력한다.
from collections import deque
n = int(input())
array = [list(map(int, input().split())) for _ in range(n)]
d = [[0 for _ in range(n)] for _ in range(n)]
d[0][0] = 1
queue = deque([])
queue.append([0, 0])
for i in range(n):
    for j in range(n):
        if d[i][j] > 0 and array[i][j] != 0:
            x = array[i][j] # 탐색하고자하는 위치의 이동가능 칸 수 입력
            if i+x <= n-1:
                d[i+x][j] += d[i][j]
            if j+x <= n-1:
                d[i][j+x] += d[i][j]

print(d[n-1][n-1])