시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 512 MB | 569 | 157 | 124 | 27.991% |
서울 Y모 대학에서 끊임없이 소음과 분진을 발생시키며 공사를 진행하던 중, 고대 유물로 추정되는 석판 하나가 발굴되었다. 이 석판은 N개의 행과 M개의 열로 나누어진 격자 형태로, 각 칸은 텅 빈 칸이거나 사람 한 명이 그려진 칸이었다. 석판은 아쉽게도 온전한 형태로 발굴되지는 않았으며, 칸들 중에는 일부가 부서져 있어 내용을 식별할 수 없는 칸도 있었다.
그 후 얼마 지나지 않아, 관련 자료를 통해 이 석판의 규칙을 알 수 있게 되었다. 이 석판에서 가능한 모든 부분 직사각형에 대해 내부의 사람 수를 구하고, 그 수들을 모두 더해서 얻는 값이 K의 배수여야 한다는 것이다. 0은 모든 수의 배수가 될 수 있다.
예를 들어, 2 × 2 크기의 아래 석판을 보자.
위 석판에는 아래와 같이 9개의 부분 직사각형이 있다.
각 부분 직사각형 내부의 합은 1, 0, 0, 1, 1, 1, 1, 1, 2가 되고, 이들의 총합은 8이 된다.
학교 측은 얻은 정보를 토대로 석판을 가능한 형태 중 하나로 복원하기 위해 연세대학교 컴퓨터과학과에 복원작업을 의뢰하었고, 자연스럽게 이 과제는 2019 교내 대회의 문제로 출제되게 되었다. 당신은 석판의 형태와 K를 입력으로 받아 석판의 복원이 가능한지 알아보고, 가능할 경우 조건을 만족하는 석판 하나를 복원해야 한다.
첫째 줄에 석판의 행의 수 N과 열의 수 M, 문제에 제시된 K가 주어진다. (1 ≤ N, M ≤ 50, 2 ≤ K ≤ 2500)
둘째 줄부터 N+1번째 줄까지, 각 줄에 M개의 정수 ai,j가 공백으로 구분되어 주어진다. (ai,j ∈ { -1, 0, 1})
ai,j = -1일 경우 석판의 i번째 행 j번째 열이 부서져 있음을, ai,j = 0 일 경우 해당 칸이 비어 있음을, ai,j = 1일 경우 해당 칸에 사람 한 명이 그려져 있음을 의미한다.
복원이 가능할 경우 첫 줄에 1을, 불가능할 경우 -1을 출력한다.
만약 첫 줄에 1을 출력했다면, 이어 N개의 줄에 M개의 정수로 행렬에 존재하는 모든 -1을 0 또는 1로 대체하여 문제의 조건에 맞게 복원한 석판 하나를 출력한다. 입력에서 -1이 아니었던 모든 칸은 입력과 동일해야 하며, -1인 모든 칸은 0 또는 1 중 하나로 복원되어야 한다.
조건을 만족하는 석판이 여러 가지라면 아무 것이나 하나만 출력한다.
2 2 8 1 0 0 -1
1 1 0 0 1
2 2 7 1 0 0 -1
-1
5 7 10 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 0 0 -1 -1 -1 -1 0 1 0 -1 -1 -1 -1 0 0 0 -1 -1 -1 -1 -1 -1 -1 -1 -1
1 1 1 1 1 1 1 1 1 1 0 0 0 1 1 1 1 0 1 0 1 1 0 0 0 0 0 0 0 1 1 1 1 1 1 1
부분 직사각형이란, 행을 위부터 1, 2, …, N으로 번호를 매기고 열을 왼쪽부터 1, 2, …, M으로 번호를 매길 때, 1 ≤ r1 ≤ r2 ≤ N, 1 ≤ c1 ≤ c2 ≤ M인 어떤 r1, r2, c1, c2에 대하여 행의 번호가 r1 이상 r2 이하이며, 열의 번호가 c1 이상 c2 이하인 모든 칸의 집합을 뜻한다. 가능한 모든 부분 직사각형이란, 부등식을 만족하는 모든 서로 다른 (r1,c1,r2,c2)에 대해 한 번씩 직사각형을 만든 것을 뜻한다.
University > 연세대학교 > 2019 연세대학교 컴퓨터과학과 프로그래밍 경진대회 D번