[백준 BOJ] 21042. Triangle of Safety

난이도

Silver III (이지만.. 이보다 더 높다고 생각함)

문제 풀이

이거 내가 풀 때는 브론즈1이 박혀 있던 어마어마한 문제였다.

동아리 학술부장님이 브론즈가 안풀린다길래 보러 갔는데, 나도 바로 안풀려서 진짜 당황했다. 문제를 간단하게 요약하자면, 삼각형으로 정이십오각형을 덮어서 모든 간선을 덮는 문제다. 모든 간선을 덮을 수 있는 삼각형을 출력해주면 되는데, 총 300개의 간선을 100개의 삼각형으로 덮으면 된다.

각 간선이 쓰여지지 않은 것만 골라서 삼각형을 만드는 방법으로 접근을 해봤는데, 그렇게 하면 80개정도만 덮인다. 그래서 조금 야매로.. 삼각형 몇개를 이미 만들었으면 좀 조건을 완화해서 삼각형을 만들도록 해봤는데, 젤 많이 줄인 횟수가 128개였다. 128개로 300개를 다 덮을 수 있었는데, 문제에서 요구하는건 아쉽지만 100개 ^^..

오~ 도대체 어떻게 푸는걸까?

대충 이쯤에서 브론즈1일리가 없다는 생각이 강하게 들었다. 그래서 문제 출처를 찾아서 본 대회 스코어보드를 봤는데, 푼 팀이 5팀밖에 없었다. 군인(진)분께서 풀이 설명하신걸 보고 그제서야 풀 수 있었는데, 삼각형 변의 길이를 unique하게 만들어버리면 됐었다.

삼각형의 변을 모두 다 다르게 구성해보자. 꼭짓점 하나를 건너뛰면 1만큼의 변이 만들어졌다고 생각하고, 비슷하게 두 개를 건너뛰면 2만큼의 변이 생겼다고 생각할 수 있다. 꼭짓점을 몇 개만큼 건너뛰냐에 따라 변의 길이가 달라지는 것이다! 진짜 발상 한 번 어렵다. 하여튼 이 삼각형을 돌리면서 출력해주면, (1, 2, 3)에 대한 간선들은 모두 덮이는 것이다.

문제에서는 정이십오각형일 때를 구하라고 한다. 그럼.. 1 ~ 12까지의 간선이 생길걸 예상할 수 있는데, 각 변이 unique한 삼각형이 몇개가 필요할까?

삼각형 하나 당 간선 3개를 커버할 수 있다. 1 ~ 12까지 모든 수가 나오게 하려면 삼각형 4개가 필요하다는 걸 알 수 있다. 공교롭게도 25 * 4 = 100이니 그 삼각형들을 찾으면 문제 정답을 맞출 수 있다.

생각없이 수를 쓰니까 해를 찾았는데, 내가 찾은 해는 \(\scriptsize (1, 2, 3), (4, 7, 11), (5, 8, 12), (6, 9, 10)\) 이다. 그냥 진짜 숫자 몇개 쓰다가 우연히 찾았다. 완전탐색으로 잘~~ 하면 찾을 수 있을 것 같긴 한데.. 여튼 이렇게 모든 수가 다 나오는 삼각형들을 찾아서 이걸 25번 돌리며 출력해주면 된다.

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using pii = pair<int, int>;
using ppii = pair<int, pii>;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    for(int i = 0; i < 25; ++i) {
        int a = i % 25, b = (i + 1) % 25, c = (i + 3) % 25;
        int d = (i + 4) % 25, e = (i + 11) % 25;
        int f = (i + 5) % 25, g = (i + 13) % 25;
        int h = (i + 6) % 25, j = (i + 15) % 25;

        cout << char('A' + a) << char('A' + b) << char('A' + c) << '\n';
        cout << char('A' + a) << char('A' + d) << char('A' + e) << '\n';
        cout << char('A' + a) << char('A' + f) << char('A' + g) << '\n';
        cout << char('A' + a) << char('A' + h) << char('A' + j) << '\n';
    }   

    return 0;
}

코드 진짜 무지성으로 짰다. ㅋㅋ

풀고나서 브론즈1은 절대 말도 안된다고 생각해서 소신대로 골드5에 기여하고 몇 분뒤에 보니, 이미 기여하신분도 의견을 바꿔서 하루만에 티어가 3개나 오른(…) 문제가 되어버렸다.

코드 전문

21042 // Triangle of Safety