격자 작업 일정
시간 제한1초메모리 제한128 MB
N x N 격자에서 각 칸이 왼쪽과 위쪽 칸이 끝난 뒤에만 시작할 수 있고 K대의 컴퓨터로 병렬 처리할 때 모든 작업을 끝내는 최소 시간을 구합니다.
문제
어떤 일은 N x N 크기의 격자로 나타낼 수 있다. 격자의 각 칸은 1초가 걸리는 작업 하나를 뜻한다.
(x, y) 칸의 작업을 시작하려면, 존재하는 경우 (x, y-1) 칸과 (x-1, y) 칸의 작업이 모두 끝나 있어야 한다.
그림은 회색 칸의 작업을 시작하기 전에 끝내야 하는 작업들을 보여준다.
이 일을 수행할 수 있는 컴퓨터가 K대 있다. 한 컴퓨터는 한 번에 한 작업만 수행할 수 있고, 각 작업을 끝내는 데는 정확히 1초가 걸린다. 매초 모든 컴퓨터를 사용할 필요는 없다.
모든 작업을 끝내는 데 필요한 최소 시간을 구하라.
입력
첫째 줄에 두 정수 N과 K가 주어진다.
1 <= N, K <= 10^9
출력
모든 작업을 끝내는 데 필요한 최소 시간을 초 단위로 출력한다.