| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 390 | 122 | 89 | 31.673% |
집순이 아리는 오랜만에 집 밖을 나와 쿠기를 만나러 학교를 가려고 한다. 이때 아리는 겸사겸사 학교로 가는 경로에 있는 장소들에서 최대한 많은 일을 처리하고 가려고 한다.
아리는 N × M 의 격자 공간에서 움직이고, 집은 격자 공간의 최좌측 상단 (0, 0), 학교는 최우측 하단(N-1, M-1)이다. 아리의 현재 위치가 (a, b)일 때, 항상 (a+1, b), (a, b+1), (a+1, b+1) 위치 중 하나로 움직인다. 단, 한 번 이동할 때마다 추가로 1분이 걸린다.
각 위치에서 할 수 있는 일들과 그 일들을 모두 수행했을 때 걸리는 시간이 주어진다. 각 장소들에서 아리는 일을 처리할지 말지 선택할 수 있으며, 한 장소에서 일을 시작하면 모든 일을 완료할 때까지 중단할 수 없고 일들을 수행하면 걸리는 시간만큼 시간이 소요된다.
명랑한 아리가 쿠기와의 약속을 위해 집에서 학교로 갈 때, 집에서 학교로 가는 경로의 장소들에서 약속까지 남은 시간 동안 가장 많이 할 수 있는 일의 양을 구하자.
정수 N과 M이 주어지고(2 ≤ N, M ≤ 50), 아리에게 남은 시간 정수 T가 분 단위로 주어진다. (N + M - 1 ≤ T ≤ 500)
먼저 i(0 ≤ i < N)번째 행 j(0 ≤ j < M)번째 열의 장소에서 할 수 있는 일들의 개수, 정수 wij(0 ≤ wij ≤ 100)가 N행 M열에 걸쳐서 주어지고,
다음으로 i(0 ≤ i < N)번째 행 j(0 ≤ j < M)번째 열의 장소에서 일들을 모두 수행했을 때 걸리는 시간, 정수 tij(0 ≤ tij ≤ 100)가 N행 M열에 걸쳐서 주어진다.
단, 집과 학교에서 아리가 할 수 있는 일은 없다.
쿠기와 학교에서 만나기로 한 약속을 지키면서, 약속까지 남은 시간 내 아리가 가장 많이 할 수 있는 일의 수를 출력한다.
6 5 15 0 2 1 3 1 3 1 4 2 2 1 4 1 3 1 2 1 4 1 7 1 3 2 3 1 4 1 1 5 0 0 1 3 2 5 4 3 5 2 3 1 2 2 2 1 3 1 2 1 2 1 3 1 2 1 3 2 1 1 0
18
N = 6, M = 5, T = 15
아리는 6행 5열 격자 공간에서 움직이는 데, 남은 시간은 15분이다.
집(0, 0)에서 (2, 1)까지 두 번 이동하여 2분이 소요 → (2, 1) 장소에서 2분을 소요하면서 일 4개를 처리 → 다음으로 (3, 2)로 이동할 때 1분 소요 → (3, 2)에서 2분을 소요하면서 일 4개를 처리 → (4, 2)로 이동할 때 1분 소요 → (4, 2)에서 1분을 소요하면서 일 2개를 처리 → (4, 3)로 이동할 때 1분 소요 → (4, 3)열에서 2분을 소요하면서 일 3개를 처리 → (5, 3)로 이동할 때 1분 소요 → (5, 3)에서 1분을 소요하면서 일 5개를 처리 → 학교(5, 4)로 이동하면서 1분을 소요하고 종료한다.
3 3 5 0 10 0 13 20 11 45 14 0 0 10 10 10 10 10 10 10 0
0
N = 3, M = 3, T = 5
아리는 3행 3열 격자 공간에서 움직이는 데, 남은 시간은 5분이다.
집(0, 0)에서 학교(2, 2)까지 경로에서 일을 하나라도 하는 순간 아리는 약속을 어기게 되기 때문에 어떤 일도 하지 못한다.