가장 긴 오르막 경로
골드 V의견: 0
탐험가 윤후는 \(N \times M\) 격자 모양의 산악 지형을 탐사한다. 칸 \((i, j)\) 에는 고도 \(h_{i,j}\) 가 적혀 있다.
탐험가는 어느 칸에서든 출발할 수 있고, 한 번에 상하좌우로 인접한 칸으로 이동할 수 있다. 단, 이동은 항상 현재 칸보다 고도가 엄격히 높은 칸으로만 가능하다(계속 올라가야 한다).
이동을 시작해 거쳐 가는 칸의 개수(출발 칸 포함)를 경로의 길이라 할 때, 만들 수 있는 가장 긴 경로의 길이를 구하여라.
- \(1 \le N, M \le 500\)
- \(0 \le h_{i,j} \le 10^9\)
첫 줄에 격자의 행 수 \(N\) 과 열 수 \(M\) 이 공백으로 구분되어 주어진다.
이어지는 \(N\) 개의 줄에 각각 \(M\) 개의 정수가 공백으로 구분되어 주어지며, 이는 각 칸의 고도이다.
엄격히 증가하는 가장 긴 경로가 거쳐 가는 칸의 개수를 한 줄에 출력한다.
2 3
1 2 3
6 5 461→2→3→4→5→6 으로 모든 칸을 거치는 길이 6의 경로가 가장 길다.
2 2
5 5
5 51모든 칸의 고도가 같아 더 높은 칸으로 이동할 수 없으므로 한 칸짜리 경로가 최대이다.
막혔나요? 코인으로 단계별 힌트를 잠금 해제하세요 — 첫 힌트는 가벼운 방향 제시, 뒤로 갈수록 더 많이 알려 줍니다. 문제를 풀면 모든 힌트가 무료로 공개됩니다.
riseoj 작성
출처 Original
평가 및 의견
가장 긴 오르막 경로
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
가장 긴 오르막 경로