시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
5 초 (추가 시간 없음) | 1536 MB | 42 | 14 | 11 | 29.730% |
로터스는 농부 존에게서 조그만 섬을 샀다. 이 섬은 아래 그림의 주황색 영역과 같이 한 변의 길이가 $n$인 계단 모양의 도형을 붙여둔 Aztec diamond 모양이다. $n$은 짝수로, 아래 그림은 $n = 6$인 경우이다.
이 섬 위의 격자점에는 농사를 지을 밭이 있다. 위 그림에서 밭이 있는 점은 빨간 점이나 파란 점으로 표시되어 있다. 파란 점은 $x + y$가 홀수인 점 $(x, y)$들로, 이 섬의 특산물이 생산되는 중요한 밭이 위치해 있다. 좌표축을 따라 난 길들은 물길이 날 수 있는 자리로, 농사를 짓기 위해서 이 길 중 몇 개를 수로로 만들어야 한다. 농사를 성공적으로 짓기 위한 조건은 다음과 같다.
그런데 수로마다 토목 공사 비용이 각기 다를 수 있다. 따라서 위의 두 조건을 모두 만족하면서 토목 공사의 비용을 최소화해야 한다. 바쁜 로터스를 도와 토목 공사에 드는 비용의 최솟값을 알려주도록 하자.
입력의 첫 줄에 영토의 크기를 나타내는 정수 $n$이 주어진다.
이후 $2n-1$개의 줄에 걸쳐 $x$축에 평행한 방향의 경계선, 즉 가로로 난 길들의 토목 공사 비용이 주어진다. $h_{x,y}$를 $(x, y)$와 $(x+1, y)$를 잇는 가로줄의 공사 비용이라고 할 때, $y$번째 줄에는 $h_{x, n - y}$가 $x$가 증가하는 순서대로 주어진다. $(1 \le y \le 2n-1)$ 줄마다 주어지는 입력의 개수는 $2$개. $4$개, $\cdots$ $2n-2$개, $2n$개, $2n-2$개, $\cdots$, $4$개, $2$개임에 주목하라.
이후 $2n-1$개의 줄에 걸쳐 세로로 난 길들의 토목 공사 비용이 주어진다. $v_{x, y}$를 $(x, y)$와 $(x, y-1)$을 잇는 길의 공사 비용이라고 할 때, $x$번째 줄에는 $v_{-n + x, y}$가 $y$가 감소하는 순서대로 주어진다. $(1 \le x \le 2n-1)$
$h_{x, y}, v_{x, y}$는 모두 양의 정수이다.
첫째 줄에 공사 비용의 최솟값을 출력한다.
2 3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3
24
Contest > BOJ User Contest > IDTcup > 제 3회 IDTcup C번