반응형
점프
-
BOJ) 점프알고리즘/백준 2020. 8. 27. 15:30
점프 1890번: 점프 문제 N×N 게임판에 수가 적혀져 있다. 이 게임의 목표는 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 점프를 해서 가는 것이다. 각 칸에 적혀있는 수는 현재 칸에서 갈 수 있는 거�� www.acmicpc.net 풀이 0,0을 시작으로 n-1,n-1까지 도달할 수 있는 경우의 수를 구하는 문제다. 각 인덱스에 적혀있는 칸만큼 오른쪽 혹은 아래로 움직일 수 있으며, 범위 밖으로는 움직일 수 없고 칸에 적힌만큼 정확히 이동해야한다. 그래서 모든 인덱스를 순차적으로 돌면서 dp 값이 0이 아니고, 해당 인덱스가 움직일 수 있는 값이 0이 아닐 때, dp를 최신화해줬다. 경우의 수를 누적시키며 답을 찾아간다고 생각하면 된다. 처음에는 dfs로 풀려고 생각하다가, 경로의 개..