시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2.5 초 | 256 MB | 340 | 115 | 90 | 37.037% |
디디학교 N명의 학생들은 N x M크기의 격자판에서 진행되는 장애물 달리기를 하려고 한다. 각 학생 i(i = 1, 2, 3, ..., N)는 처음에 (i, 1)의 위치에 서 있으며, 결승선 M열 즉, (1, M), (2, M), (3, M), ..., (N, M)의 어느 위치에라도 도착하는 것이 목표이다. 학생들은 한 번 이동할 때 상하좌우로 인접한 곳으로 이동하며, 각 위치로 이동하는 데 걸리는 시간은 같거나 다르다. 또한 학생들은 항상 결승선까지 가장 빨리 도착할 수 있는 경로로 이동한다. 교장선생님 디디는 결승선의 각 지점에 도착하는 학생 수만큼 생수를 배치하려고 한다. 이때 (i, M)에 각각 몇 개의 생수를 배치해야 하는 지 구하는 프로그램을 작성하라.
첫째 줄에 격자판의 크기를 나타내는 N, M(1 ≤ N, M ≤ 500)이 공백으로 구분되어 주어진다.
둘째 줄부터 N개의 줄에는 각각 M개의 정수가 공백으로 구분되어 주어진다. 입력의 i+1번째 줄의 j번째 정수는 격자판에서 (i, j)로 이동할 때 걸리는 시간을 의미하며, 이 값은 104 이하의 양의 정수이다. 단, i번째 학생이 이미 (i, 1)에 위치해 있으므로 시작 시 미리 밟고 있는 땅은 이동할 때 걸리는 시간에 포함되지 않지만, 결승선으로 이동하는 시간은 포함된다. 또한 한 학생이 가장 빨리 도착할 수 있는 도착지점은 유일하게 주어짐이 보장된다.
첫째 줄부터 N개의 줄에 각각 (i, M)의 위치에 몇 개의 생수를 배치해야 하는지 출력하라.
4 4 3 4 5 2 1 6 2 8 1 3 4 5 6 2 1 10
1 0 3 0
각 학생은 아래와 같은 경로로 이동한다.
학생 1 : (1, 1) -> (1, 2) -> (1, 3) -> (1, 4)
학생 2 : (2, 1) -> (3, 1) -> (3, 2) -> (3, 3) -> (3, 4)
학생 3 : (3, 1) -> (3, 2) -> (3, 3) -> (3, 4)
학생 4 : (4, 1) -> (4, 2) -> (4, 3) -> (3, 3) -> (3, 4)
Contest > BOJ User Contest > 네블컵 > 제2회 네블컵 J번