문제
앞에서부터 읽어도, 뒤에서부터 읽어도 똑같은 것을 회문(Palindrome) 이라고 한다.
예를 들어, 배열 [ 2, 1, 4, 3 ] 은 회문이 아니지만, [ 1, 5, 3, 5, 1 ] 은 회문이다.
N 행 M 열의 표에 숫자들이 채워져 있다.
정올이는 이 표가 "회문 표" 가 되기를 원한다.
회문 표란, 표의 모든 행과, 모든 열이 각각 회문이 되는 표를 의미한다.
위 그림이 회문 표의 예시다.
1행을 보면 [ 3, 3, 1, 1, 3, 3 ] 으로 회문이다.
1열을 봐도 [ 3, 4, 2, 4, 3 ] 으로 회문이다.
이런 식으로 모든 행과 모든 열을 각각 검사해도 회문이 되면 회문 표가 된다.
하나라도 회문이 되지 않으면 회문 표라고 할 수 없다!
이제, 정올이는 N행 M열의 표를 입력 받는다.
입력 받은 표를 회문 표로 만들기 위해, 정올이는 원하는 칸을 선택하여 원하는 수로 바꾸는 작업을 한다.
회문 표를 만들기 위한 최소 작업 횟수를 구하자.
입력
첫 줄에 행의 개수 N과, 열의 개수 M이 입력된다. ( 1 ≤ N, M ≤ 1,000 )
이후 N 행 M 열의 표 정보가 입력된다. ( 표에 적힌 수들은 1,000,000 이하의 자연수 )
출력
회문 표를 만들기 위한 최소 작업 횟수를 출력하자.
부분문제
| 번호 | 점수 | 조건 |
|---|---|---|
| #1 | 10점 | N = M = 2 |
| #2 | 10점 | N = M = 3 |
| #3 | 30점 | N, M 이 모두 짝수 |
| #4 | 30점 | 표에 적힌 수들은 모두 10 이하다. |
| #5 | 20점 | 제약 조건 없음 |
예제 #1
3 4
1 2 3 1
3 1 1 3
2 2 1 3
4
예제 #2
3 3
1 2 1
3 4 3
1 2 1
0
이미 조건을 만족한다.
예제 #3
4 6
1 2 3 1 2 1
3 1 2 1 2 1
2 2 1 1 3 4
3 2 3 3 2 1
8
위 방법 외에도, 8칸만 수정하여 회문 표를 만드는 다른 방법들이 있습니다.
태그
출처
Russian Olympiad in Informatics October 21, 2017 Basic F번
로그인해야 코드를 작성할 수 있어요.