백준 32205번 - 네모의 꿈(C++)

문제

• 백준, 실버 4, 문제 링크
• 풀이 날짜: 2025.04.28
• 풀이 시간: 15:59~17:37(1시간 38분)
• 사용 언어: C++

문제 해설

문제: n개의 삼각형과 각 변의 길이가 주어질 때,

같은 길이의 변을 맞닿게 붙여서 네모를 만들 수 있는지 확인해보자.

이때 각 변의 길이는 최대 100만이다.

N의 최댓값은 50만이므로, 가능한 시간 복잡도는 최대 O(NlogN)이다.

네모가 만들어지려면 다음 조건을 만족해야 한다.

 

1. 같은 길이를 갖는 변이 존재해야 한다
2. 길이가 같은 변을 이어붙였을 때 나타날 수 있는 두 가지 이상의 방법 중, 사각형이 되는 경우의 수가 있을 때

처음 생각했을 때, 길이가 같은 변을 이어붙일 때 사각형이 되는 경우의 수가 존재할 수도 있다고 생각했다. 그래서 모두 검사해 보기로 했다.

그렇다면 삼각형이 되는 경우는 어떤 경우일까?

 

아이디어 1: 각도로 계산하기

같은 길이를 갖는 변 a(in 삼각형 A)와 변 b(in 삼각형 B)가 있다고 하자(a의 길이 = b의 길이).

변 a에 대해 양쪽의 각을 alpha, beta라 하자. 또한, 변 b에 대해 변 끝에 생기는 각을 alpha', beta'라 하자.

삼각형이 되려면 변 a와 변 b를 딱 붙였을 때 alpha + alpha' = 90 deg가 되어야 각 하나가 사라져야 한다.

또 beta + beta' = 90 deg가 되어도 똑같이 삼각형이 되는데, 생각해보면 alpha와 beta는 변 a를 뒤집게 되면 바뀌게 된다. 즉,

$ alpha + alpha' != 90 && beta + beta' != 90 $이거나

$ beta + alpha' != 90 && alpha + beta' != 90 $이면 사각형이다(단, 단위는 각도의 도).

 

그런데 각도 값을 구하는 건 어려우므로 다른 방식으로 접근할 필요가 있었다.

 

아이디어 2: 코사인 법칙 이용하기

여기서 생각해볼 수 있는 것은, 각도를 그대로 이용하기는 어려우니 cos 값을 이용하자는 것이다.

삼각형의 세 변의 길이가 주어져 있을 때, 코사인 법칙을 사용하면 삼각형의 모든 각별로 코사인 값을 구할 수 있다.

 

코사인 법칙

삼각형 ABC를 고려하자. 코사인 제2법칙이란 각 A, B, C의 대변을 각각 a, b, c라 할 때 다음이 성립한다는 법칙이다.

$ a2b2c2​=b2+c2−2bccosA=c2+a2−2cacosB=a2+b2−2abcosC​ $

 

삼각형을 그려서 다시 확인해본 결과, 두 선분이 이어진 하나의 선분이 되려면 cos(alpha) + cos(alpha') = 0이어야 한다.

세 선분 a, b, c 중 길이가 같은 선분을 a라 할 때, cos(alpha)와 cos(beta)는 코사인 법칙에 의해

$ cos(alpha)=(a^2+c^2-b^2)/2ca $

$ cos(beta)=(a^2+b^2-c^2)/2ab $

 

로 계산할 수 있다.

즉, 다음 중 하나에 해당한다면 이는 사각형이다.

$ cos(alpha) + cos(alpha') != 0 && cos(beta) + cos(beta') != 0 $

$ cos(beta) + cos(alpha') != 0 && cos(alpha) + cos(beta') != 0 $

이때 코사인 값은 실수이므로, 오차를 피하기 위해 각 값의 0.1% 이하의 차이는 무시하도록 설계했다.

참고: https://stackoverflow.com/questions/24999861/determining-if-two-numbers-are-almost-equal-and-outputting-the-result

#include <cmath>
#include <algorithm>

bool ApproximatelyEqual(double a, double b)
{
    return std::abs(a - b) < 0.001 * std::max(std::abs(a), std::abs(b));
}

이를 구현하면 위와 같다.

 

이를 수행할 알고리즘은 이렇다.

알고리즘 1

N개 삼각형 중 두 개를 골라 변의 길이가 같은 것이 있는지 비교해야 한다.

이때, 하나의 경우가 실패하더라도 다른 경우도 고려해야 한다.

모든 삼각형을 두 개씩 골라서 순회하려면 $ O(N^2) $의 순회가 필요하므로, 최적화가 필요하다.

map[k]에 k의 변의 길이를 갖는 삼각형의 번호를 기록한다. 이때 두 개 이상 삼각형을 저장해야 하므로 vector를 value로 둔다. 이후 순회시에 남은 두 변의 cos을 구하고, 이를 통해 계산을 수행하자.

 

이렇게 하면 같은 변을 갖는 삼각형의 번호가 이미 주어져 있으므로, 그것들끼리 두 개 삼각형을 고르는 비용만 필요하게 된다. 이 또한 $ N^2 $의 시간이 필요하지만, 같은 변을 갖는 삼각형끼리만 고려하면 되므로, 큰 문제가 되지 않을 거라고 생각했다.

 

그런데 실제로 풀어보니, 시간 초과가 나왔다. ApproximatelyEqual을 구현할 때부터 약간 잘못된 느낌이 들었는데, 아니나 다를까 같은 변을 갖는 삼각형끼리 비교하는 시간이 $ N^2 $이어서 너무 시간이 많이 걸린 것 같았다.

 

아이디어 3: 변의 길이가 같을 때 삼각형이 되는 경우는 없다

풀다가 막혀서 아예 다른 분의 풀이를 참고했는데, 알고 보니 ‘변의 길이가 같을 땐 삼각형이 될 수가 없었다’.

조건에서 명시된 바에 따르면 삼각형의 변의 길이 a, b, c는 $ 1 \le a < b < c \le 10^6 $이다.

다시 삼각형이 되기 위한 조건을 생각해보자. 변의 길이가 같은 삼각형 두 개를 이어 붙였을 때 삼각형이 되기 위해서는, 어느 한 방향으로 붙였을 때에도 삼각형이 되고, 뒤집어서 붙여도 삼각형이 되어야 한다.

이렇게 되려면 다른 삼각형 하나가 아래와 같이 이등변 삼각형이 되어야 한다.

왼쪽의 삼각형, 오른쪽의 삼각형을 붙였을 때.

삼각형을 다른 방식으로 붙였을 때에도 똑같이 결과가 삼각형이려면, 위 그림에서 $ \alpha $와 $ \beta $가 같아야 한다.

하나의 변을 끼고 있는 두 개 $ \alpha $, $ \beta $가 같다는 것은, 오른쪽에 붙인 삼각형이 이등변 삼각형이라는 뜻과 같다.

그러나 이는 문제의 조건에 모순이다. 이등변 삼각형이 되려면, a, b, c 중 두 변이 같은 길이를 가져야 하는데, 문제의 조건에 의해 a<b<c이기 때문이다.

따라서 두 개의 삼각형이 같은 길이의 변을 갖는다면 무조건 사각형이 되는 경우가 하나 이상 존재한다고 볼 수 있다.

 

그래서, $ N \le 50만 $의 조건을 만족하며 풀려면, 아예 변의 길이가 같은 것이 발견되면 바로 1을 반환하는 식으로 접근하면 되겠다.

가장 빠르게 해결할 방법은 이렇게 되겠다.

1. 삼각형을 순차적으로 조사하며, 어떤 변의 길이가 등장했는지 기록한다.
2. 변 a, b, c 중 같은 길이의 삼각형이 이미 있었다면 사각형이 존재하므로 1을 반환한다.

이를 구현하기 위해서는 existSide라는 bool 배열을 두어, 변의 길이 a, b, c가 들어올 때 existSide[a] = existSide[b] = existSide[c] = true로 기록하면 되겠다.

그리고 a, b, c와 같은 길이의 삼각형이 있었는지는 existSide[a] || existSide[b] || existSide[c]로 조사한다.

#include <iostream>

using namespace std;

int main()
{
    int n, a, b, c;
    
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> n;
    
    bool existSide[1000001] = { false, };

    for (int i = 0; i < n; i++)
    {
        cin >> a >> b >> c;

        if (existSide[a] || existSide[b] || existSide[c])
        {
            cout << "1";
            return 0;
        }

        existSide[a] = true;
        existSide[b] = true;
        existSide[c] = true;
    }

    cout << "0";

    return 0;
}

 

문제 조건을 통해서, 좀 더 쉽게 변형할 수 있는지, 내가 생각하는 경우가 실제로 나올 수 있는 경우인지 고려하기 위해 직접 그림을 그려보는 연습을 계속 해야 할 것 같다.

실제로 가능한 경우인가? 이를 고민하는 습관을 들이자.