https://www.acmicpc.net/problem/1890
처음 시간초과 코드
- dfs
n = int(input())
board = []
memo = [[0] * n for _ in range(n)]
dx = [0, 1]
dy = [1, 0]
memo[0][0] = 1
for i in range(n):
board.append(list(map(int, input().split())))
def move(dir, loc, memo):
x, y = loc
if x == n-1 and y == n-1:
memo[n-1][n-1] += 1
return
distance = board[x][y]
nx = x + dx[dir] * distance
ny = y + dy[dir] * distance
if 0 <= nx < n and 0 <= ny < n:
if memo[nx][ny] == 0:
memo[nx][ny] = memo[x][y]
else:
memo[nx][ny] =+ 1
move(0, (nx, ny), memo)
move(1, (nx, ny), memo)
return
else:
return
move(0, (0,0), memo)
move(1, (0,0), memo)
print(memo[n-1][n-1])
- memoization 적용
n = int(input())
board = []
# 메모 배열 초기화
memo = [[-1] * n for _ in range(n)]
for i in range(n):
board.append(list(map(int, input().split())))
# DFS 함수 정의
def dfs(x, y):
# 도착 지점에 도달하면 경로 하나 추가
if x == n - 1 and y == n - 1:
return 1
# 이미 계산된 값이 있으면 반환
if memo[x][y] != -1:
return memo[x][y]
memo[x][y] = 0 # 현재 위치에서 시작하는 경로 수 초기화
distance = board[x][y]
# 오른쪽 이동
if y + distance < n:
memo[x][y] += dfs(x, y + distance)
# 아래로 이동
if x + distance < n:
memo[x][y] += dfs(x + distance, y)
return memo[x][y]
answer = dfs(0,0)
# 시작점에서 DFS 실행
print(answer)
- Bottom Up
import sys
input = sys.stdin.readline
n = int(input()) # row의 길이
board = [input().split() for _ in range(n)]
m = len(board[0]) # col의 길이
dp = [[0]*m for _ in range(n)]
dp[0][0]=1
def sol():
for i in range(n):
for j in range(m):
k = int(board[i][j])
# 이동 가능한 거리가 0이라면 넘어간다.
# 또는 dp가 0이라는 것은 현재 위치에 도달할 수 없음을 의미함으로 넘어간다.
if k == 0 or dp[i][j] == 0:
continue
if i+k < n: # 아래쪽으로 이동하는 경우, 게임판을 벗어나지 않는다면 경우의 수 추가
dp[i+k][j] += dp[i][j]
if j+k < m: # 오른쪽으로 이동하는 경우, 게임판을 벗어나지 않는다면 경우의 수 추가
dp[i][j+k] += dp[i][j]
return dp[-1][-1] # 가장 오른쪽 아래에 담긴 경우의 수를 return
print(sol())728x90
