Go, Vantage point
가까운 곳을 걷지 않고 서는 먼 곳을 갈 수 없다.
Github | https://github.com/overnew/
Blog | https://everenew.tistory.com/
티스토리 뷰
반응형
문제
https://algospot.com/judge/problem/read/JUMPGAME
algospot.com :: JUMPGAME
외발 뛰기 문제 정보 문제 땅따먹기를 하다 질린 재하와 영훈이는 땅따먹기의 변종인 새로운 게임을 하기로 했습니다. 이 게임은 그림과 같이 n*n 크기의 격자에 각 1부터 9 사이의 정수를 쓴 상
algospot.com
풀이
간단한 다이나믹 프로그래밍 문제
해당 위치에서 끝에 도달이 가능한지의 여부를 is_pos_board에 저장해두어 중복된 호출을 방지하여 최적화한다.
해당 위치의 도달 여부가 기록되어있다면 바로 그 값을 반환하고 아니라면
왼쪽과 오른쪽으로 이동하는 경우를 재귀호출하여 반환된 값을 기록한다.
코드
반응형
'알고리즘 공부 > 알고스팟' 카테고리의 다른 글
| [알고스팟] LIS - Longest Increasing Sequence/ 최대 증가 부분 수열 (C++) (0) | 2020.12.10 |
|---|---|
| [알고스팟] WILDCARD - Wildcard/와일드 카드 (C++) (0) | 2020.11.09 |
| [알고스팟] QUADTREE - 쿼드 트리 뒤집기 (C++) (0) | 2020.10.30 |
| [알고스팟] CLOCKSYNC - Synchronizing Clocks (C++) (0) | 2020.10.18 |
| [알고스팟] BOARDCOVER - 게임판 덮기 (C++) (359) | 2020.10.16 |
댓글