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

---

접근법

이차원 배열(벡터)에서 index를 다루고 놀아야 하는 중요한 문제이다. 문제를 보면 삼각형 A와 B중 하나만 회전, 반전 시키면서 B와 비교하면 찾을 수 있다고 생각이 들 것이다. 따라서 가능한 경우의 수를 해당 Index의 변화를 고려하여 접근한다면 조금 수월하게 접근할 수 있다.

먼저 각 삼각형의 원소들을 받아오기 위해서 부터 이중 for문이 요구된다. 첫번째 줄엔 1개, 2번째 줄엔 2개 등 각 줄에 맞춰서 받아와야 하는 원소가 증가한다. 따라서 첫번째 for문의 index를 s32_I라 하며고 두번째 index를 s32_J라 하면 한 삼각형의 줄의 개수를 s32_Cnt로 받아온 후 s32_I는 0부터 s32_Cnt보다 작을때 까지, s32_J는 s32_I보다 같거나 작을 때 까지 반복해서 원소를 받아오면 각 줄의 개수가 늘어날 때 마다 적절히 받아올 수 있다.

삼각형 A가 회전,대칭하여 나올 수 있는 경우의 수는 총 6가지로, 원본, 120도 회전, 240도 회전 그리고 각 회전에서의 대칭인 경우이다. 대칭이동은 단순히 각 줄의 마지막부터 접근하여 바꿔주면 되기에 비교적 쉽다. 240도 회전 역시 120도 회전을 2번 해 주면 되기에, 결국 120도 회전을 구현할 수 있냐 없냐의 문제로 결정되어진다.

120도의 회전은 시계방향, 반시계방향 2가지가 존재한다.

각 회전에 대한 index의 변화는 위와 같다. 이중 for문으로 해당 변화를 표현해야 하기에 각 자리마다의 변화를 확인하면 다음과 같다.

오른쪽은 오른쪽으로 120도 회전한 경우이다.  0,0 -> 2,0이고 1,0 -> 2,1이므로 원래 삼각형의 행이 변화하면 변화되는 위치의 열이 변함을 알 수 있다. 따라서 원래의 1,1은 1,0 기준에서 행이 변화했기에, 변화되는 위치의 열이 변해야 하지만 행과 열이 모두 변함을 알 수 있다. 이는 동일한 이중 for문 내에서 서로다른 변화 특징을 보이기에 정확히 표현할 수 없다. 띠라서 왼쪽으로 120도 회전하는 것을 기준으로 이를 표현해야 한다.

---

정답

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int32_t s32_Cnt;
vector<vector<int32_t>> st_TriangleA, st_TriangleB;

vector<vector<int32_t>> MakeRotation120(const vector<vector<int32_t>>& st_RotateTriangle) {
    vector<vector<int32_t>> st_Tmp(s32_Cnt, vector<int32_t>(s32_Cnt, 0));

    for (int32_t s32_I = 0; s32_I < s32_Cnt; s32_I++) {
        for (int32_t s32_J = 0; s32_J <= s32_I; s32_J++) {
            st_Tmp[s32_Cnt - s32_J - 1][s32_Cnt - s32_I - 1] = st_RotateTriangle[s32_I][s32_J];
        }
    }
    return st_Tmp;
}

vector<vector<int32_t>> MakeRotation240(const vector<vector<int32_t>>& st_RotateTriangle) {
    // 120도 회전 2번
    vector<vector<int32_t>> st_Tmp = MakeRotation120(st_RotateTriangle);
    return MakeRotation120(st_Tmp);
}

vector<vector<int32_t>> reflect(const vector<vector<int32_t>>& st_RotateTriangle) {
    vector<vector<int32_t>> st_Tmp(s32_Cnt, vector<int32_t>(s32_Cnt, 0));
    // 배열 순서 변경 -> 대칭
    for (int32_t s32_I = 0; s32_I < s32_Cnt; s32_I++) {
        for (int32_t s32_J = 0; s32_J <= s32_I ; s32_J++) {
            st_Tmp[s32_I][s32_I - s32_J] = st_RotateTriangle[s32_I][s32_J];
        }
    }

    return st_Tmp;
}

int32_t CalculateDifference(const vector<vector<int32_t>>& st_RotatedTriangle) {
    int32_t s32_Diffrence = 0;

    for (int32_t s32_I = 0; s32_I < s32_Cnt; s32_I++) {
        for (int32_t s32_J = 0; s32_J <= s32_I; s32_J++) {
            s32_Diffrence += abs(st_RotatedTriangle[s32_I][s32_J] - st_TriangleB[s32_I][s32_J]);
        }
    }
    return s32_Diffrence;
}

int32_t main() {

    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    cin >> s32_Cnt;
    st_TriangleA.resize(s32_Cnt, vector<int32_t>(s32_Cnt, 0));
    st_TriangleB.resize(s32_Cnt, vector<int32_t>(s32_Cnt, 0));

    for (int32_t s32_I = 0; s32_I < s32_Cnt; s32_I++) {
        for (int32_t s32_J = 0; s32_J <= s32_I; s32_J++) {
            cin >> st_TriangleA[s32_I][s32_J];
        }
    }

    for (int32_t s32_I = 0; s32_I < s32_Cnt; s32_I++) {
        for (int32_t s32_J = 0; s32_J <= s32_I; s32_J++) {
            cin >> st_TriangleB[s32_I][s32_J];
        }
    }

    // 원상태 및 대칭
    int32_t s32_Result = CalculateDifference(st_TriangleA);
    vector<vector<int32_t>> st_RotatedTriangle = reflect(st_TriangleA);
    s32_Result = min(s32_Result, CalculateDifference(st_RotatedTriangle));

    // 120도 및 대칭
    st_RotatedTriangle = MakeRotation120(st_TriangleA);
    s32_Result = min(s32_Result, CalculateDifference(st_RotatedTriangle));

    st_RotatedTriangle = reflect(st_RotatedTriangle);
    s32_Result = min(s32_Result, CalculateDifference(st_RotatedTriangle));

    // 240도 및 대칭
    st_RotatedTriangle = MakeRotation240(st_TriangleA);
    s32_Result = min(s32_Result, CalculateDifference(st_RotatedTriangle));

    st_RotatedTriangle = reflect(st_RotatedTriangle);
    s32_Result = min(s32_Result, CalculateDifference(st_RotatedTriangle));

    cout << s32_Result << endl;

    return 0;
}