백준 1548 부분 삼각 수열

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

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> arr;

int main() {

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

    int n;
    cin >> n;


    arr.resize(n);

    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    if (n <= 2) {
        cout << n;
        return 0;
    }

    sort(arr.begin(), arr.end());

    int ans = 2;

    for (int i = 0; i < n - 1; i++) {
        for (int j = n - 1; j >= 0; j--) {
            if (i + 1 == j) {
                break;
            }
            if (arr[i] + arr[i + 1] > arr[j]) {
                ans = max(ans, j - i + 1);
            }
        }
    }

    cout << ans;




    return 0;
}

1. 문제

길이가 n(<=50)인 배열이 주어진다. 이 배열에서 적당히 숫자를 뽑아 삼각 수열을 만드려고 한다. 삼각 수열은 수열 내 임의로 원소 3개를 뽑았을 때 x+y>z, x+z>y, y+z>x를 만족하는 수열이다. 이 수열의 최대 길이를 구하는 문제이다.

2. 풀이

 if (n <= 2) {
        cout << n;
        return 0;
    }

    sort(arr.begin(), arr.end());

 우선 주어진 수열의 길이가 2보다 작을 경우 항상 삼각 수열을 만족하는 것으로 간주하여 배열의 길이를 그대로 출력하고프로그램을 종료한다.

 주어진 수열에서 임의로 원소를 추출하여 삼각 수열을 만들 예정이므로 배열의 순서는 고려하지 않는다. 따라서 배열을 정렬할 수 있다. 

    int ans = 2;

    for (int i = 0; i < n - 1; i++) {
        for (int j = n - 1; j >= 0; j--) {
            if (i + 1 == j) {
                break;
            }
            if (arr[i] + arr[i + 1] > arr[j]) {
                ans = max(ans, j - i + 1);
            }
        }
    }

 이후 이중 반복문을 돈다. 현재 수열이 삼각 수열인지 확인하려면 해당 수열의 가장 큰 z와 가장 작은 x, y에 대해 x+y>z를 만족하면 된다. 다른 숫자에 대해서는 x, y가 커지고, z가 작아지므로 항상 부등호를 만족하기 때문이다. i는 가장 작은 수에 대한 포인터, j는 가장 큰 수에 대한 포인터로 두고 x+y>z를 확인한다. 조건이 맞는다면 ans를 갱신한다. 

 모든 경우를 돌았음에도 조건에 맞지 않은 경우 두 개의 수열을 뽑았을 때 항상 삼각수열을 만족하는 것으로 간주했으므로 2를 출력하도록 ans를 초기화하였다.

 연산이 끝난 후 ans를 출력하면 정답을 구할 수 있다.