시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 61 | 22 | 14 | 35.897% |
신도시의 도시 계획을 세우려고 한다. 신도시의 어느 곳에 고층 빌딩과 공원을 지을지 결정해야 한다. 신도시는 R x C 개의 단지로 구성되어 있으며, R개의 행 C개의 열로 구성된 격자 모양으로 나타낸다. 예를 들어, 아래 그림은 2개의 행과 3개의 열로 구성된 신도시를 나타낸다. 총 여섯 개의 단지가 있다. 각각의 단지는 해발 고도를 나타내는 정수 값을 하나씩 가지고 있다.
신도시에 고층 빌딩과 공원을 지을 때는 아래 조건을 모두 만족해야 한다.
3번 조건 때문에, 도시 계획을 세울 때는 음이 아닌 정수 Z를 먼저 골라야 한다. 그 다음, 해발 고도가 Z 이하인 모든 단지에 고층 건물을 짓고, 나머지 단지에는 공원을 지으려고 한다. 공원은 두 개의 인접한 단지 위에 지어야 한다. 두 단지가 도로를 공유할 때, 두 단지를 인접하다고 한다.
공원 하나를 짓는데는 D원이 필요하다. 고층 빌딩 전체를 짓는 비용은 Z×W원이다.
위의 모든 조건을 만족하면서, 고층 빌딩과 공원을 짓는 비용의 최솟값을 구하는 프로그램을 작성하시오.
첫 줄에 4개의 정수 R, C, D, W 가 주어진다 (1 ≤ R, C ≤ 50 그리고 1 ≤ D, W ≤ 109). 다음 R줄에는 각 줄에 C개의 정수가 주어진다. 이 수는 각 단지의 y값을 나타낸다. 각 y값은 1 이상 109 이하이다.
첫 줄에 고층 건물과 공원을 모든 단지에 짓는데 필요한 최소 비용을 출력하라.
2 3 120 10 10 30 20 40 20 10
340
Z = 10을 고르면 고층 건물을 두 단지에 짓고 (10×10 = 100원) 나머지 네 단지에 두 개의 공원을 짓게 된다 (120×2 = 240원). 총 비용이 340원이고, 이 예제에서의 최소 비용이다.
만약 Z = 0을 고를 경우 총 360원이 필요하며, Z = 40을 고를 경우 총 400원이 필요하다. Z = 20을 고른다면, 총 네 단지에 고층 건물을 짓게 되는데, 이 경우 남아있는 두 단지에 공원을 지을 수 있는 방법이 없다. 이는 아래 그림에서 확인할 수 있다.
1 2 76 59 62 77
76
1 4 71 87 41 2 95 68
142
3 3 16 12 58 90 8 81 38 94 12 56 80
160
4 4 71 3 85 86 97 99 30 74 50 88 77 78 34 83 59 26 54 63
297
Python을 사용하는 참가자는 PyPy 사용을 권장 합니다.
위의 그림 예제의 경우에, Z를 10으로 고른다면 좌상단과 우하단에 위치한 단지에 고층 건물을 짓고, 나머지 단지에는 공원을 두 개 지을 수 있다.
아래 세 예제는 이 규칙을 따르지 않고 공원을 지은 경우를 나타낸다.
왼쪽 예제는 공원이 도시 격자를 벗어난 경우를 나타낸다. 중간 예제는 두 개의 공원이 겹쳐서 하나의 단지 위에 지어진 경우를 나타낸다. 상단 중간 단지를 공유하고 있다. 우측 예제는 공원이 두 개의 인접한 단지 위에 지어지지 않은 경우를 나타낸다. 이 세 경우 모두 공원을 잘못 지은 경우이다.