[백준] 1548번 : 부분 삼각 수열 (C++)

1548번 : 부분 삼각 수열

---

문제)

세 수 x, y, z가 x+y>z, x+z>y, y+z>x의 관계를 만족하면, 세 수는 삼각관계에 있다고 한다.

마찬가지로 길이가 N인 수열 B(b[0], b[1], ..., b[n-1])의 모든 b[i], b[j], b[k]가 삼각관계에 있으면 이 수열은 삼각 수열이라고 한다. 이때, i, j, k는 모두 다른 값이다.

수열 A가 주어졌을 때, 이 수열에서 적절히 몇 개의 원소를 빼서 이 수열을 삼각 수열로 만들려고 한다. 삼각 수열의 최대 길이를 구하는 프로그램을 작성하시오.

 

 

 

입력 :

첫째 줄에 수열의 크기 N이 주어진다. 둘째 줄에 수열 A에 들어있는 수가 공백을 사이에 두고 주어진다. N은 최대 50이고, A에 들어있는 수는 109보다 작거나 같은 자연수이다.

 

 

출력 :

첫째 줄에 가장 긴 부분 삼각 수열의 길이를 출력한다.

 

 

 

 

 

풀이)

 

// 1548. 부분 삼각 수열
#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int n;
vector<int> vec;
 
int main()
{
    cin >> n;
    vec.resize(n);
    for (auto& ele : vec) cin >> ele;
 
    sort(vec.begin(), vec.end());
 
    int ans = 1;
    for (int i = 0; i < n - 1; i++)
    {
        for (int j = n - 1; j > i + 1; j--)
        {
            if (vec[i] + vec[i + 1] > vec[j])
            {
                ans = max(ans, j - i + 1);
                break;
            }
        }
    }
 
    if (ans == 1 && n >= 2) ans = 2;
 
    cout << ans;
 
    return 0;
}

---

출처 : https://www.acmicpc.net/problem/1548 

1548번: 부분 삼각 수열