문제) 백준 - 동적 계획법 (Dynamic Programming) - 점프
-> www.acmicpc.net/problem/1890
1890번: 점프
첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장
www.acmicpc.net
오른쪽이나 아래로 점프가 가능한 경우 dp 리스트에 +1 해준다. (0, 0)부터 시작해 (n - 1, n - 1)까지 재귀로 완전 탐색하며 (n - 1, n - 1)일 때 기저 사례를 처리해 1을 반환한다.
소스 코드)
import sys
sys.setrecursionlimit(1000000)
input = sys.stdin.readline
n = int(input())
graph = []
for _ in range(n):
graph.append(list(map(int, input().split())))
dp = [[-1] * n for _ in range(n)]
def dfs(x, y):
#기저 사례
if x == n - 1 and y == n - 1:
return 1
if dp[x][y] == -1:
dp[x][y] = 0
if 0 <= x + graph[x][y] < n:
dp[x][y] += dfs(x + graph[x][y], y)
if 0 <= y + graph[x][y] < n:
dp[x][y] += dfs(x, y + graph[x][y])
return dp[x][y]
print(dfs(0, 0))
반응형
'PS(Problem Solving) > 백준_BOJ' 카테고리의 다른 글
[백준] 11054번 - 가장 긴 바이토닉 부분 수열 (파이썬) 문제 및 풀이 (0) | 2021.03.09 |
---|---|
[백준] 11722번 - 가장 긴 감소하는 부분 수열 (C++, 파이썬) 문제 및 풀이 (0) | 2021.03.09 |
[백준] 1520번 - 내리막 길 (C++, 파이썬) 문제 및 풀이 (0) | 2021.03.09 |
[백준] 1904번 - 01타일 (C++/파이썬) 문제 및 풀이 (0) | 2021.03.04 |
[백준] 14502번 - 연구소 (파이썬) 문제 및 풀이 (0) | 2021.03.03 |
댓글