| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 0.5 초 | 1024 MB | 84 | 39 | 23 | 41.818% |
기러기 토마토 스위스 인도인 별똥별 우영우...
위의 단어들은 모두 거꾸로 읽어도 똑같은 팰린드롬이다. 승재는 위의 대사를 너무 감명 깊게 들은 나머지, 팰린드롬에 빠져 2차원 팰린드롬을 떠올리고 말았다. 2차원 팰린드롬이란, $N\times M$크기의 행렬이 주어졌을 때, 좌우대칭과 상하대칭을 모두 만족하는 팰린드롬을 의미한다. 우리는 0과 1만으로 이루어진 2차원 비트 행렬이 주어졌을 때, 이 행렬을 일정한 연산을 통해 2차원 비트 팰린드롬으로 만들고자 한다. 이때 필요한 최소 연산 횟수를 구하여라.
연산은 다음 과정을 통해 이루어진다.
O가 비트를 전환하는 부분이라고 했을 때, 아래는 유효한 연산이다.
$(K=2)$
아래는 유효하지 않은 연산이다.
$(K=1)$
$(K=1)$
입력은 아래와 같이 주어진다.
$N$ $M$ $K$
$A_{1,1}$ $A_{1,2}$ ... $A_{1,M}$
...
$A_{N,1}$ $A_{N,2}$ ... $A_{N,M}$
첫 줄에 2차원 비트 팰린드롬을 만들기 위한 최소 연산 횟수를 출력한다. 만약 2차원 비트 팰린드롬을 만들 수 없는 경우, -1을 출력한다.
6 6 2 100100 101000 101101 101101 000101 001001
2
첫 번째 연산
두 번째 연산
위의 두 연산을 거치면 팰린드롬이 된다.
6 4 1 1010 1010 1010 1010 1010 1011
-1
University > 연세대학교 > 2022 연세대학교 프로그래밍 경진대회 J번