[C++] 삼각형만들기 (백준 2622번)

https://www.acmicpc.net/problem/2622

 

#include <iostream>
using namespace std;

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

    int n;
    cin >> n;

    int ans = 0;

    // i <= j <= k 를 만족하도록 찾기
    for (int i = 1; i < n - 1; i++) {
        for (int j = i; j < n - 1; j++) {
            int k = n - i - j;
            if (k < j) break;
            if (i + j > k) ans++;
        }
    }

    cout << ans << '\n';
}

첨에는 합동이 뭔지 살짝 헷갈렸다. 

생각해보니 3개의 변의 길이가 모두 같으면 SSS 합동으로, 어떻게 조합해도 하나의 삼각형으로 본다.

즉, i <= j <= k 가 되도록 하여 조합을 해서 하나씩 세어주면 되는 문제! (AC)

 

    // i <= j <= k 를 만족하도록 찾기
    for (int i = 1; i < n - 1; i++) {
        for (int j = i; j < n - 1; j++) {
            int k = n - i - j;
            if (k < j) continue;
            if (i + j > k) ans++;
        }
    }

아 처음에는 위 코드처럼 k < j 일 때 continue 하도록 했는데 너무 오래 걸리는 것 같아서 다른 사람들 코드 염탐하다가 그냥 break를 해주면 된다는 것을 깨달았다.

 

 

시간 단축!

 

---

 

참고: 삼각형의 합동 조건