별 지도 경로
골드 I의견: 0
\(R \times C\) 크기의 격자에 별들이 놓여 있다. 각 칸 \((i, j)\)에는 정수 밝기 \(a_{i,j}\)가 있다.
별의 체인은 칸의 순서열 \((r_1, c_1), (r_2, c_2), \dots, (r_k, c_k)\)로, 각 연속된 두 칸 \((r_t, c_t) \to (r_{t+1}, c_{t+1})\)에서 \(r_t < r_{t+1}\), \(c_t < c_{t+1}\), \(a_{r_t, c_t} < a_{r_{t+1}, c_{t+1}}\)가 모두 성립해야 한다.
만들 수 있는 가장 긴 체인의 길이를 구하여라.
- \(1 \le R, C \le 32\)
- \(R \times C \le 1\,000\)
- \(1 \le a_{i,j} \le 10^6\)
첫째 줄에 격자의 행 수 \(R\)과 열 수 \(C\)가 공백으로 구분되어 주어진다.
다음 \(R\)개의 줄에 각 행의 \(C\)개 밝기 값이 공백으로 구분되어 주어진다.
가장 긴 체인의 길이를 출력한다.
3 3
1 7 3
5 2 8
4 6 9
3
행, 열, 값이 모두 엄격히 증가하는 체인 중 가장 긴 것은 예를 들어 \((0,0,1) \to (1,1,2) \to (2,2,9)\)로 길이 \(3\)이다. 값이 \(1 \to 2 \to 9\)로 증가하고 행과 열도 \(0 \to 1 \to 2\)로 엄격히 증가한다.
2 2
5 5
5 5
1
모든 셀의 값이 \(5\)로 같으므로 값이 엄격히 증가하는 체인이 없어 답은 \(1\)이다.
riseoj 작성
출처 Original
평가 및 의견
별 지도 경로
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
별 지도 경로