증가 배열 만들기 timer 1s memory 1024MB

N\times M 크기의 2차원 배열이 있다. 당신은 배열의 각 칸에 1 이상 K 이하의 정수를 채워 넣어 배열을 증가 상태로 만들고자 한다.

배열이 증가 상태라는 것 (1,1)에서 출발해서 (N,M)을 향해 오른쪽이나 아래쪽으로 이동할 때 가능한 모든 경로에 대해, 각 경로에서 방문한 칸의 수를 처음부터 일렬로 나열한 수열이 오름차순임을 의미한다.

• 오른쪽이나 아래쪽으로 이동한다는 것은, (i,j)에서 (i,j+1)또는 (i+1,j)로 움직인다는 것이다. 단, 배열 밖으로는 이동할 수 없다.

• 수열 A_{1}, A_{2}, \dots, A_{k}가 오름차순이라는 것은 A_{1} \lt A_{2} \lt \cdots \lt A_{k} 임을 의미한다.