[BOJ 2242 // C++] 삼각형 만들기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 2242번 문제인 삼각형 만들기이다.
문제는 아래 링크를 확인하자.

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

2242번: 삼각형 만들기

N과 L 모두 40 이하의 수만 입력으로 들어오므로, 모든 막대기의 길이의 합은 1600 이하가 됨을 관찰하자.

또한 삼각형을 구성하기 위해서는 한 변의 길이가 다른 두 변보다 길어지면 안 되므로, 삼각형을 구성하는 각 변의 길이는 1066 이하가 됨을 관찰하자. (변의 길이가 정수가 될 수밖에 없음을 확인하자.)

 

두 변의 길이가 정해지면 남은 변의 길이는 전체 길이에서 두 변의 길이를 뺀 것으로 구할 수 있으므로, 첫 막대기부터 k번째 막대기까지 사용했을 때(모든 막대를 사용할 필요는 없다) 구성가능한 첫 두 변의 길이의 순서쌍(0을 포함한다)을 k-1번째 막대기까지 사용했을 때 구성가능한 첫 두 변의 길이의 순서쌍을 이용해 1067*1067의 knapsack DP를 하듯이 계산하는 것으로 모든 두 변의 길이의 후보를 구해낼 수 있다. (1067*1067*40은 1억보다 충분히 작은 값임을 확인하자.)

 

가능한 세 변의 길이의 후보를 모두 찾았다면 헤론의 공식(Heron's formula)를 이용해 변의 길이만으로 (삼각형의 넓이 * 100)의 제곱의 최댓값을 구해내고, 제곱했을 때 이 수 이하가 되는 가장 큰 수를 이분탐색으로 찾아 문제를 해결하자. 헤론의 공식은 다음과 같다.

 

삼각형의 넓이를 \(S\)라 하고 \(s = (a+b+c)/2\)로 정의할 때, \(S = \sqrt{s(s-a)(s-b)(s-c)}\)

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
typedef long double ld;

int N, total;
int arr[1067][1067];

ll ans;

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

	cin >> N;
	arr[0][0] = 1;
	while (N--) {
		vector<pair<int, int>> vec;
		int x; cin >> x;
		total += x;
		for (int r = 0; r < 1067; r++) {
			for (int c = 0; c < 1067; c++) {
				if (arr[r][c]) continue;
				if (r >= x && arr[r - x][c]) vec.emplace_back(make_pair(r, c));
				else if (c >= x && arr[r][c - x]) vec.emplace_back(make_pair(r, c));
			}
		}
		for (auto& p : vec) {
			arr[p.first][p.second] = 1;
		}
	}

	for (ll a = 1; a < 1067; a++) {
		for (ll b = a; b < 1067; b++) {
			if (arr[a][b]) {
				ll c = total - (a + b);
				if (a + b < c || b + c < a || c + a < b) continue;
				ans = max(ans, (a + b + c) * (a + b - c) * (a - b + c) * (-a + b + c));
			}
		}
	}

	ans *= 625;
	if (ans == 0) cout << -1;
	else {
		ll L = 1, R = 64000000;
		while (L < R) {
			ll mid = (L + R) / 2 + 1;
			if (mid * mid <= ans) L = mid;
			else R = mid - 1;
		}

		cout << L;
	}
}