문제
문제 : https://www.acmicpc.net/problem/1890
각 칸에 수가 적힌 N * N 크기의 게임판이 있다. 게임의 목표는 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 점프하여 이동하는 것이다.
각 칸에 적힌 수는 현재 칸에서 갈 수 있는 거리를 뜻한다. 단, 0은 종착점을 의미한다. 오른쪽이나 아래쪽으로만 이동할 수 있고, 한 번 점프하는 중간에 방향을 바꿀 수 없다.
가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 이동할 수 있는 경로의 수를 구하여라.
접근
2024.04.08 - [백준] 11048 - 이동하기와 비슷한 문제인데, '이동하기'는 한 번에 한 칸씩 움직이는 반면 '점프'는 이동할 수 있는 칸의 수가 정해져 있지 않다.
때문에 현재 위치한 방을 어떻게 왔는지가 아니라, 현재 위치한 방에서 도착할 수 있는 방이 어딘지 고려해야 한다.
'이동하기' 문제와 동일하게 동적 계획법을 활용했고, 테이블에는 각 칸에 도달할 수 있는 경로의 수를 저장했다.
풀이
1. 게임판 크기 입력
N = int(sys.stdin.readline())
2. 게임판 입력
game = [list(map(int, sys.stdin.readline().strip().split())) for i in range(N)]
3. 테이블 초기화
테이블에는 각 칸에 도달할 수 있는 칸의 수를 저장할 수 있도록 0으로 초기화한다.
dp = [[0 for _ in range(N)] for _ in range(N)]
4. 테이블 업데이트
게임 시작 시 가장 왼쪽 위칸에서 시작한다. 이 칸은 시작하면서 도착한 것과 같으므로 1로 업데이트한다.
for i in range(N):
for j in range(N):
# 게임판 시작
if i == 0 and j == 0:
dp[i][j] = 1그리고 현재 칸에서 도착할 수 있는 칸의 좌표를 업데이트한다. 다른 칸에 도착하기 위해서는 현재 좌표의 칸에 도착한 적이 있어야 하고, 현재 좌표의 칸이 종착점이 아니어야 한다.
if dp[i][j] > 0 and game[i][j] > 0:
# 이동한 좌표 확인
if i + game[i][j] < N:
# 테이블 업데이트
dp[i + game[i][j]][j] += dp[i][j]
if j + game[i][j] < N:
dp[i][j + game[i][j]] += dp[i][j]현재 좌표가 다른 칸으로 갈 수 있는 좌표라면 오른쪽 방향으로 이동한다. 이동할 때는 이동한 후의 좌표가 게임판 밖으로 나가지 않도록 해야 한다. 그리고 저장하는 값은 현재 좌표 칸에 도달할 수 있는 경로의 수화 이동한 후의 좌표에 도달할 수 있던 경로의 수의 합으로 한다.
그리고 아래쪽도 동일하게 처리한다.
5. 결괏값 출력
테이블에서 종착지 좌표의 값을 출력한다.
print(dp[-1][-1])
전체 소스는 다음과 같다.
import sys
N = int(sys.stdin.readline())
game = [list(map(int, sys.stdin.readline().strip().split())) for i in range(N)]
dp = [[0 for _ in range(N)] for _ in range(N)]
for i in range(N):
for j in range(N):
# 게임판 시작
if i == 0 and j == 0:
dp[i][j] = 1
if dp[i][j] > 0 and game[i][j] > 0:
if i + game[i][j] < N:
dp[i + game[i][j]][j] += dp[i][j]
if j + game[i][j] < N:
dp[i][j + game[i][j]] += dp[i][j]
print(dp[-1][-1])