| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 15 | 8 | 7 | 58.333% |
대학생 선우는 건축가 제이크한테 감리 실습을 받고 있다. 선우가 현장에서 건물을 시찰해서 설계도를 그리면 제이크가 설계도를 잘 그렸는지 확인한다. 설계도는 가로 $M$픽셀, 세로 $N$픽셀 크기의 흑백 그림이다.
선우와 제이크는 예상치 못한 문제에 직면했다. 선우가 설계도를 복사해서 제이크에게 줄 때 설계도에 쌓인 먼지도 같이 복사되어서 제이크가 설계도를 알아볼 수 없게 되었다. 선우가 빈 종이를 여러 번 복사하면서 확인해본 결과 양옆 또는 위아래로 인접한 두 픽셀에 동시에 먼지가 쌓이지 않는다는 것을 깨달았다.
선우는 먼지의 성질을 적절히 활용하면 제이크가 원래 설계도를 다시 복원할 수 있을 거라고 생각한다. 선우는 설계도를 복사하기 전에 손가락을 이용하여 한 행 또는 열에 있는 모든 먼지를 제거할 수 있다. 먼지는 금방 다시 쌓이기 때문에 선우는 먼지를 $C$회 이하로 쓸어서 설계도를 복원할 수 있게 하려고 한다. 선우와 제이크를 도와 설계도를 복원하는 프로그램을 작성하여라.
여러분은 아래 두 함수를 구현해야 한다.
int[] wipe_dust(int subtask, int[][] B)
int[][] restore_blueprint(int subtask, int[][] X)
제출하는 소스 코드의 어느 부분에서도 입출력 함수를 실행해서는 안 된다.
여러분의 프로그램은 두 번 실행된다. 첫 번째 실행에서는 wipe_dust 함수만 호출하며 두 번째 실행에서는 restore_blueprint 함수만 호출한다. 프로그램의 실행 시간은 두 번의 실행 시간을 합한 값이며 메모리 사용량은 두 번의 사용 메모리 중 최댓값으로 계산된다.
모든 데이터에 대해서, $3 \leq N, M \leq 1\,000$ 을 만족한다.
위 왼쪽 그림과 같이 도면 [[0, 1, 0, 0], [1, 1, 1, 0], [0, 1, 0, 0]] 을 복사하는 경우를 생각해보자. 그레이더는 wipe_dust(1, [[0, 1, 0, 0], [1, 1, 1, 0], [0, 1, 0, 0]])를 호출한다.
여러분이 [2]를 반환했다면 이는 선우가 $2$행을 문지르고 도면을 복사했다는 것을 의미한다. 이후 도면에 먼지가 일부 달라붙은 상태로 복사되면 위 오른쪽 그림과 같이 복사된다.
그레이더는 restore_blueprint(1, [[1, 1, 1, 0], [1, 1, 1, 1], [1, 1, 1, 0]])을 호출한다.
여러분은 restore_blueprint 함수에서 [[0, 1, 0, 0], [1, 1, 1, 0], [0, 1, 0, 0]]를 반환해야 한다.
샘플 그레이더는 첫 번째 줄에 $subtask, N, M$을 입력받는다. 두 번째 줄부터 $N$개의 줄에는 도면의 정보 $B[i][j]$에 해당하는 $M$개의 정수를 사이 공백 없이 입력받는다.
다음 줄부터 $N$개의 줄에는 먼지의 정보 $D[i][j]$에 해당하는 $M$개의 정수를 사이 공백 없이 입력받는다. $i+1$행 $j+1$열에 도면에 먼지가 쌓인다면 $D[i][j] = 1$이고 그렇지 않다면 $D[i][j] = 0$이다.
샘플 그레이더는 wipe_dust 함수와 restore_blueprint 함수를 한 번씩 호출하며, 도면의 성공적인 복원 여부(Correct 또는 Wrong)를 출력한다.
실제 채점에서 사용하는 그레이더는 샘플 그레이더와 다를 수 있음에 유의하여라.
Contest > BOJ User Contest > FunctionCup > FunctionCup 2023 WX번
C++17, C++20, C++17 (Clang), C++20 (Clang)