Algorithm/Baekjoon
1890번 파이썬
@Eeap
2022. 4. 11. 22:48
반응형
https://www.acmicpc.net/problem/1890
1890번: 점프
첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장
www.acmicpc.net
이 문제는 처음에 bfs로 접근할까 하다가 dp로 문제를 접근해봤다.
먼저 이 문제의 조건은 그 칸에 있는 수만큼 점프를 해야하고 점프는 오른쪽 또는 아래쪽 무조건 한방향으로만 쭈욱 점프할 수 있다.
문제 풀이는
처음부터 n-1까지 row와 col을 반복해서 각각에 현재 인덱스의 점프거리를 추가해서 새로운 r(아래쪽 점프)과 c(오른쪽 점프)로 만들고 새로운 행에 그 전 dp의개수를 추가해주는 방식으로 구현했다.
import sys
input = sys.stdin.readline
n=int(input())
ary = [list(map(int,input().split())) for _ in range(n)]
p = [[0 for _ in range(n)] for __ in range(n)]
p[0][0]=1
for row in range(n):
for col in range(n):
if row==n-1 and col==n-1:
break
r=row+ary[row][col]
if r <n:
p[r][col]+=p[row][col]
c=col+ary[row][col]
if c <n:
p[row][c]+=p[row][col]
print(p[n-1][n-1])
반응형