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])
반응형