[백준 28217번] 두 정삼각형 (C++)

문제링크 : https://www.acmicpc.net/problem/28217

28217번: 두 정삼각형

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int N, M, result = MAX;
int arr1[11][11], arr2[11][11];

void check()
{
    int cnt1 = 0, cnt2= 0;
    for(int i=0; i<N; i++)
    {
        for(int j=0; j<=i; j++)
        {
            if(arr1[i][j]!=arr2[i][j]) cnt1++; //다를때마다 카운팅
            if(arr1[i][i-j] != arr2[i][j]) cnt2++; //뒤집어서도 확인 (대칭 확인)
        }
    }
    result = min({result, cnt1, cnt2}); //가장 작은 값 저장
}

void rotate() //120도 회전
{
    int tmp[11][11];
    for(int i=0; i<N; i++)
    {
        for(int j=0; j<=i; j++)
        {
            tmp[i][j] = arr1[N-j-1][i-j];
        }
    }

    memcpy(arr1, tmp, sizeof(tmp)); //회전한 배열 복사
}

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);

    cin >> N;
    for(int i=0; i<N; i++) //첫번째 삼각형
    {
        for(int j=0; j<=i; j++)
        {
            cin >> arr1[i][j];
        }
    }

    for(int i=0; i<N; i++) //두번째 삼각형
    {
        for(int j=0; j<=i; j++)
        {
            cin >> arr2[i][j];
        }
    }

    for(int i=0; i<3; i++) //회전하며 체크
    {
        check();
        rotate();
    }

    cout << result;
    
    return 0;
}

구현 문제이다.

두가지 삼각형을 입력받고, 첫 번째 삼각형에 대해 120도 회전 및 대칭 시켜줌으로써 두 번째 삼각형과의 차이를 카운팅한다.

 

처음에 변하지 않은 상태에서 그대로 체크를 해준다.

이때 뒤집힌 경우도 같이 체크를 해준다.

 

그러고 나서 120도 회전을 돌린다.

회전을 돌리고 다시 체크를 한다.

이때 마찬가지로 뒤집어서도 확인을 한다.

 

마지막 으로 한번더 돌리면서 확인을 한다.

3번째부터는 원상태로 돌아오기 때문에 처음 포함(변화x 상태) 총 3번만 체크하면 된다.

 

120도 회전에 대해서는 아래와 같이 규칙을 찾았다.

tmp : arr
i j : i j
0 0 : 2 2
1 0 : 1 1
1 1 : 2 1
2 0 : 0 0
2 1 : 1 0
2 2 : 2 0

tmp는 120도 돌린 것을 저장할 임시배열이고, arr이 기존 첫 번째 삼각형이다.

해당 값들을 보면 tmp의 i는 N-j의 값인 것을 알 수 있고, tmp의 j은 arr 기준 i-j의 값인 것을 알 수 있다.

위 문제에서는 i=1부터가 아닌 0부터 시작했으므로 N-j에 1을 추가로 빼주어야 한다.