출처 : https://www.acmicpc.net/problem/1890

문제

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

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

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

입력

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

출력

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

---

아이디어

현재 위치의 인덱스에 value값을 더하는 방법
(x,y) : value -> (x+value,y) or (x,y+value)
$...$
if (x+value,y) or (x,y+value) == (n-1, n-1):
cnt += 1
최종 (n-1, n-1)까지 도달.

---

코드

Mine 1 (Memory Error)

import sys
input = lambda: sys.stdin.readline()

n = int(input())
data = [[int(x) for x in input().split()] for y in range(n)]
data[n-1][n-1]  = 1
cnt = 0
dp = []
if data[0][0] < n:
    dp += [data[0][0],0], [0,data[0][0]]
len_dp = len(dp) # 2
while len_dp:
    for m in range(len(dp)):
        if dp[m][0]+data[dp[m][0]][dp[m][1]] < n: #아랫쪽으로
            dp += [[dp[m][0]+data[dp[m][0]][dp[m][1]],dp[m][1]]]
        if dp[m][1]+data[dp[m][0]][dp[m][1]] < n: # 오른쪽으로
            dp += [[dp[m][0],dp[m][1]+data[dp[m][0]][dp[m][1]]]]
    del dp[:len_dp]
    cnt += dp.count([n-1, n-1])
    len_dp = len(dp)
print(cnt)

개선사항

dp.count -> memory 초과.(예상)

---

Clone

n=int(input())
games=[]
for i in range(n):
	game=list(map(int,input().split()))
    games.append(game)

dp=[[0 for i in range(n)] for i in range(n)]
dp[0][0]=1
for i in range(n):
	for j in range(n):
		if i==0 and j==0:
        	continue
        for k in range(j):
        	if k+games[i][k]==j:
            	dp[i][j]+=dp[i][k]
			for k in range(i):
            	if k+gmaes[k][j]==i:
                	dp[i][j]+=dp[k][j]
print(dp[n-1][n-1])

출처 : https://codedrive.tistory.com/246

개선사항