https://www.acmicpc.net/problem/1890
1890번: 점프
문제 N×N 게임판에 수가 적혀져 있다. 이 게임의 목표는 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 점프를 해서 가는 것이다. 각 칸에 적혀있는 수는 현재 칸에서 갈 수 있는 거리를 의미한다. 반드시 오른쪽이나 아래쪽으로만 이동해야 한다. 0은 더 이상 진행을 막는 종착점이며, 항상 현재 칸에 적혀있는 수만큼 오른쪽이나 아래로 가야 한다. 한 번 점프를 할 때, 방향을 바꾸면 안 된다. 즉, 한 칸에서 오른쪽으로 점프를 하거나, 아래로
www.acmicpc.net
bfs, dfs 둘 다 시간초과 나는 걸 보고 DP로 풀어야겠다고 직감함.
풀이 접근방법은 예전에 풀었던 '등굣길'과 거의 동일하다.
[Python] 프로그래머스. 등굣길 (Level 3)
https://programmers.co.kr/learn/courses/30/lessons/42898 코딩테스트 연습 - 등굣길 | 프로그래머스 계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에..
inspirit941.tistory.com
table[y][x] = "현재 위치까지 도달할 수 있는 방법의 수" 라고 정의한다면
처음에 주어진 2d array를 maps라고 정의할 경우 maps[y][x] = 현재 위치에서 다음 위치로 점프할 수 있는 거리.
즉 점화식은
1. table[y + maps[y][x]][x] = table[y + maps[y][x]][x] + table[y][x] - 아래로 이동할 경우
2. table[y][x + maps[y][x]] = table[y][x + maps[y][x]] + table[y][x] - 오른쪽으로 이동할 경우
두 가지가 된다.
'프로그래밍 > 코딩테스트 문제풀이' 카테고리의 다른 글
| [Python] Hackerrank. Find the Nearest Clone (Medium) (0) | 2020.03.09 |
|---|---|
| [Python] 프로그래머스. 2018 카카오 recruit - 프렌즈4블록 (Level 2) (0) | 2020.03.07 |
| [Python] 백준 14500. 테트로미노 (0) | 2020.03.04 |
| [Python] 프로그래머스. 2018 카카오 recruit - 압축 (Level 2) (0) | 2020.03.03 |
| [Python] 백준 11724. 연결 요소의 개수 (0) | 2020.03.02 |