728x90
오늘의 문제
외발뛰기(ID: JUMPGAME)
https://algospot.com/judge/problem/read/JUMPGAME
algospot.com :: JUMPGAME
외발 뛰기 문제 정보 문제 땅따먹기를 하다 질린 재하와 영훈이는 땅따먹기의 변종인 새로운 게임을 하기로 했습니다. 이 게임은 그림과 같이 n*n 크기의 격자에 각 1부터 9 사이의 정수를 쓴 상
algospot.com
나의 풀이
import sys
sys.stdin = open('input.txt', 'r')
def solve(si, sj, a):
global tmp
tmp[si][sj] = a
dij = ((1, 0), (0, 1))
x = board[si][sj]
for di, dj in dij:
ni, nj = si + x * di, sj + x * dj
if 0 <= ni < N and 0 <= nj < N and tmp[ni][nj] == -1:
solve(ni, nj, a+1)
for _ in range(int(input())):
N = int(input())
board = [list(map(int, input().split())) for _ in range(N)]
tmp = [[-1] * N for _ in range(N)]
solve(0, 0, 0)
print('YES' if tmp[N-1][N-1] != -1 else 'NO')
오늘의 회고
- 동적 계획법에 대해 이해했다.
- 시작부터 동적 계획법으로 문제를 풀기 보다는, 재귀함수로 푼 후 메모이제이션을 이용하자.
728x90
'PS > Algorithm-Python' 카테고리의 다른 글
| [이코테] 기출문제/그리디 - 2. 곱하기 혹은 더하기 (0) | 2025.09.23 |
|---|---|
| [이코테] 기출문제/그리디 - 1. 모험가 길드 (0) | 2025.09.23 |
| [99클럽] 코테 스터디 5일차 TIL (0) | 2024.04.30 |
| [종만북] 분할정복 - 쿼드트리 QUADTREE (1) | 2024.04.21 |