31725번 - 포닉스와 달구 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1.5 초 | 1024 MB | 117 | 58 | 49 | 50.000% |
문제
포닉스와 달구는 $N \times N$ 크기의 격자 위에서 놀이를 하려고 한다. 이 격자의 $i$행 $j$열에 위치한 칸에는 가중치 $A_{i, j}$가 있다. 놀이의 방법은 아래와 같다.
- 달구는 $K \times K$ 크기의 영역을 하나 골라서, 해당 영역의 칸들을 윤이에게 선물로 준다. 단, 달구가 선물할 영역에는 격자의 $1$행 $1$열과 $N$행 $N$열이 포함되면 안 된다.
- 포닉스는 처음에 격자의 $1$행 $1$열에 있고, $N$행 $N$열에 도달할 때까지 이동한다. 포닉스는 현재 위치한 칸이 $r$행 $c$열일 때, $r+1$행 $c$열 또는 $r$행 $c+1$열로 이동할 수 있다. 단, 격자 밖이나 윤이가 선물받은 칸으로는 이동할 수 없다.
- 포닉스가 얻을 수 있는 점수는 포닉스가 지나간 칸에 포함된 가중치의 합이다.
포닉스는 점수를 최대로 얻고자 하고, 달구는 포닉스의 점수가 최소가 되도록 영역을 고르고자 한다. 포닉스와 달구는 모두 최선을 다해 놀이를 진행한다고 가정했을 때, 포닉스가 얻을 수 있는 점수의 최댓값을 구해보자.
입력
첫째 줄에 격자의 크기 $N$과 $K$가 공백으로 구분되어 주어진다. $(2 \le N \le 2\ 000; 1 \le K < N)$
다음 $N$개의 줄에는 $N$개의 정수 $A_{i, 1}, A_{i, 2}, \cdots, A_{i, N}$이 공백으로 구분되어 주어진다. $(0 \le A_{i, j} \le 10\ 000)$
출력
포닉스가 얻을 수 있는 점수의 최댓값을 출력한다.
예제 입력 1
5 3 4 8 13 2 5 0 7 7 3 12 25 3 11 5 6 9 12 0 28 3 1 13 5 8 9
예제 출력 1
65
출처
University > UNIST-DGIST-POSTECH > 2024 UNIST-DGIST-POSTECH 연합 프로그래밍 경진대회 (2024 UDPC) > Senior Division I번
University > UNIST-DGIST-POSTECH > 2024 UNIST-DGIST-POSTECH 연합 프로그래밍 경진대회 (2024 UDPC) > Open Contest L번
- 문제를 만든 사람: bnb2011
- 문제를 검수한 사람: 99asdfg, hyperbolic, leo020630, lky7674, mjhmjh1104, nick832, queued_q, slah007, tony9402, utilforever
© 2026 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호