https://www.acmicpc.net/problem/1520
1520번: 내리막 길
여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으
www.acmicpc.net
'내리막'이라는 조건 때문에 쉽게 풀릴 것 같았는데..
...시간 초과가 났었던가?
지금 풀이를 다시 보니 DP 개념을 활용했었네...
DFS와 DP를 활용했고,
특정 지점에 도달했을 때, 해당 지점에서 목적지로 갈 수 있는 방법의 수를 chk배열에 저장했다.
따라서, chk가 -1 이라면 아직 방문한 적 없고,
0이라면 갈 수 있는 방법이 없다는 뜻.
현재 위치를 기준으로 다음 위치가 '내리막'이라면,
다음 위치의 chk를 확인하여 현재 chk에 더해주는 방법으로 해결하였다.
'C++ > CodingTest' 카테고리의 다른 글
| [백준 2606] 바이러스.cpp (0) | 2022.08.25 |
|---|---|
| [백준 1766 - 골드 2] 문제집.cpp (0) | 2022.05.06 |
| [백준 1620 - 실버 4] 나는야 포켓몬 마스터 이다솜.cpp (0) | 2022.05.06 |
| [백준 1476 - 실버 5] 날짜 계산.cpp (0) | 2022.05.06 |
| [백준 1475 - 실버 5] 방 번호.cpp (0) | 2022.05.06 |