백준 1548 부분 삼각 수열 c++ (완전탐색)

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

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보다 작거나 같은 자연수이다.

출력

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

알고리즘 분류

• 그리디 알고리즘
• 브루트포스 알고리즘
• 정렬

풀이

그리디한 아이디어가 필요한 완전 탐색 문제이다.

우선 i, j, k가 삼각관계인지 확인하려면

k가 가장 큰 값이고, i와 j가 작은 수일 때 i + j >k 를 만족하는지 확인하면 된다.  

작은 수들과 큰 수를 비교한다? 배열을 정렬하면 편할 것 같다.

요소의 순서는 상관없으니 정렬을 해도 상관없다.

주어진 배열을 정렬하면,

arr[n]이 삼각 수열이라고 할 때,

arr[0] + arr[1] > arr[n-1]을 만족한다면 n-1 과 a 사이에 있는 모든 수들이 삼각관계이다.(그리디)

즉, A[n]이 주어질 때, A[n]의 부분 삼각 수열 arr[] 중 가장 길이가 긴 부분 삼각 수열을 찾으면 되는 것이다.(완전 탐색)

 

A = {1, 2, 3, 4 , 10}이라 하자,

1 + 2 > 3 false

1 + 2 > 4 false

1 + 2 > 10 false

2 + 3 > 4 true / 부분 삼각 수열의 길이 3

2 + 3 > 10 false

3 + 4 > 10 false

 

부분 삼각 수열은  arr = {2, 3, 4}가 될 것이며, 길이는 3이다.

 

4번 예제도 한 번 확인해 보자.

A = {1, 1, 1, 100, 100, 100} //편의를 위해 뒤에 3개의 값은 100으로 썼다.

1 + 1 > 1  true / 부분 삼각 수열의 길이 3

1 + 1 > 100  false  / false면 3 개의 수 중 가장 큰 값은 더 이상 확인하지 않아도 될 것 같다!

1 + 1 > 100  false / 이번엔 인덱스 1,2,3 을 검사한 경우이다, 위의 경우와 값은 같으나 위의 경우는 인덱스 0,1,3을 검사한 경우

1 + 100 > 100 true /  인덱스 2,3,4를 검사한 경우이며 부분 삼각 수열의 길이는 3

1 + 100 > 100 true / 인덱스 2,3,5를 검사한 경우이며 부분 삼각 수열의 길이는 4

100 + 100 > 100 true / 인덱스 3,4,5를 검사한 경우이며 부분 삼각 수열의 길이는 3

 

가장 긴 부분 삼각 수열의 길이는 4로 정답이 제대로 나온 것을 볼 수 있다.

 

본인은 세 개의 값중 가장 큰 값(third)을 뒤에서 부터 검사하였는데,

위의 풀이대로, 두 번째로 큰 값(second)의 인덱스에 +1부터 검사하며, false인 경우 스킵하는 것이 깔끔할 것 같다.

 

주어진 수열의 길이가 2 이하인 경우, 항상 삼각 수열이라고 친다.

이는, 주어진 수열의 길이가 3이상인 경우 결과값의 최솟값은 2임을 의미하기도 한다.

 

코드

#include <iostream>
#include <algorithm>
using namespace std;
int n;
//1<=n<=50
long long arr[50];
bool deleted[50];
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}
	int result = 1;
	sort(arr, arr+n);

	for (int first = 0; first < n - 1; first++) {
		for (int third = n - 1; third >= 0; third--) {
			if (first + 1 == third) break;
			if (arr[first] + arr[first + 1] > arr[third]) {
				result = max(result, third - first + 1);
				break;
			}
		}
	}
	if (result == 1 && n >= 2) {
		result = 2;
	}
	cout << result;
}