문제
첫 번째 줄에는 1개의 수를, 두 번째 줄에는 2개의 수를, . . . , N번째 줄에는
N개의 수를 아래 그림과 같이 배치한 정삼각형 A, B가 주어진다. 각 위치에 있는 수는 0 또는 1이다.
당신은 정삼각형을 시계방향 또는 반시계 방향으로 120◦ 회전시키거나 좌우로 대칭시킬 수 있다.
예를 들어, 위 그림의 정삼각형 A를 회전시켜서 얻을 수 있는 정삼각형들은 다음과 같다.
A를 대칭시켜서 얻을 수 있는 정삼각형은 다음과 같다.
두 정삼각형의 차이는 두 정삼각형을 겹쳤을 때 값이 다른 위치의 개수이다.
예를 들어, 정삼각형 A와 B를 겹쳐보면, 두 번째 줄에서 가장 왼쪽,
세 번째 줄에서 가장 왼쪽과 오른쪽에 있는 수들이 다르므로, A와 B의 차이는 3이 된다.
반면에, A를 반시계 방향으로 120◦ 회전시킨 삼각형(두 번째 그림에서 오른쪽 삼각형)과 B를 겹쳐보면
세 번째 줄에서 왼쪽에서 두 번째에 있는 수들만 다르므로, 이때 정삼각형의 차이는 1이 된다.
정삼각형 A와 B가 주어진다. 당신은 A를 원하는 만큼 회전시키고 대칭시킬 수 있다.
물론 A를 회전시키 거나 대칭시키지 않아도 된다.
또한, 회전시키거나 대칭시킬 수 있는 횟수에는 제한이 없다.
위와 같이 A를 회전시키거나 대칭시켜 B와 차이가 최소로 나게 하자.
이때 차이가 얼마인지 구하시오.
제약 조건
• 주어지는 모든 수는 정수이다.
• 1 ≤ N ≤ 10
• A, B의 각 위치에 있는 수는 0또는 1이다.
입력
첫 번째 줄에 A, B의 크기 N이 주어진다.
두 번째 줄부터 N + 1번째 줄까지, A의 각 위치에 있는 수들이 주어진다.
i + 1(1 ≤ i ≤ N)번째 줄에는 A의 i번째 줄에 있는 i개의 정수가 왼쪽부터 공백을 사이에 두고 순서대로 주어진다.
N + 2번째 줄부터 2N + 1번째 줄까지, B의 각 위치에 있는 수들이 주어진다.
i + N + 1(1 ≤ i ≤ N)번째 줄에는 B의 i번째 줄에 있는 i개의 정수가 왼쪽부터 공백을 사이에 두고 순서대로 주어진다.
출력
첫 번째 줄에 A를 원하는 만큼 회전, 대칭시켜서 얻을 수 있는 B와의 차이의 최솟값을 출력한다.
부분문제
| 번호 | 점수 | 조건 |
|---|---|---|
| #1 | 5점 | A에 배치되어 있는 모든 수들이 같다. 다시 말해 A에는 모두 0이 써 있거나, 모두 1이 써 있다. |
| #2 | 10점 | |
| #3 | 40점 | A를 회전시킨 경우만 고려해도 정답을 찾을 수 있다 |
| #4 | 45점 | 추가 제한 없음. |
예제1
3
0
10
100
0
00
001
1
A를 반시계 방향으로 120˚ 돌리면 B와 한 곳만 값이 다르게 된다. 이외에도 다양한 방법으로 차이를 1로 만들 수 있다.
예제2
4
0
11
100
1000
0
00
001
1110
0
예제3
4
0
10
001
1100
0
01
000
0111
2