[BOJ/백준 1448][C++] 삼각형 만들기

문제

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

 

문제 내용

입력받은 빨대들 중에서 3개를 뽑아 삼각형을 만드는 문제이다.
삼각형으로 만들 수 없다면 -1 출력하고, 만들 수 있다면 세 변의 길이의 합의 최댓값을 출력한다.

 

문제 풀이

삼각형을 이루기 위해서는 (가장 긴 변의 길이) < (나머지 두 변의 길이의 합) 을 만족해야 한다.
문제를 보면, 최댓값을 구하고자 하므로, 길이를 정렬하여, 뒤에서부터 조건에 맞는지를 확인하면 된다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

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

	//입력
	int n,tmp; 
	cin >> n; //빨대 개수
	vector<int>v;
	for (int i = 0; i < n; i++) {
		cin >> tmp;
		v.push_back(tmp);
	}

	//문제 해결
	sort(v.begin(), v.end()); //빨대 길이 정렬
	int a, b, c; //a<=b<=c 
	int result = 0;
	for (int i = n-1; i >= 2; i--) {
		c = v[i]; //가장 긴 변
		b = v[i - 1];
		a = v[i - 2];
		if (c >= a + b) continue; //삼각형 만들 수 없음
		else {
			result = a + b + c;
			cout << result << '\n';
			return 0;
		}
	}

	cout << -1 << '\n'; 
}

 

문제 코드 설명

1) 입력

빨대 개수를 입력받고, 길이를 vector에 저장한다.

 

2) 문제 해결

빨대의 길이를 정렬하고, 반복문을 돌면서 삼각형 조건을 확인한다.
끝까지 삼각형을 만들 수 없으면 반복문을 빠져나가 -1이 출력되고, 중간에 조건에 맞는 것이 있으면 길이의 합을 출력하고 프로그램을 종료한다.