[BOJ 6057 // C++] Building A Fence

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

 

이번에 볼 문제는 백준 6057번 문제인 Building A Fence이다.
문제는 아래 링크를 확인하자.

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

6057번: Building A Fence

네 양수 a, b, c, d로 사각형을 구성할 수 있을 필요충분조건은 a+b+c>d, a+b+d > c, a+c+d>b, b+d+c>a 네 식을 동시에 만족시키는 것이다. 각 부등식의 좌변을 a+b+c+d가 되게끔 양변에 항을 더하고 양변을 2로 나누면 a, b, c, d는 각각 (a+b+c+d)/2 미만이어야 한다는 조건으로 바꿔 생각할 수 있다.

 

위의 조건을 만족하는 a,b,c,d를 반복문을 이용해 세고 문제를 해결하자. a와 b를 정해둘 때 가능한 (c, d)의 경우의 수를 O(1) 계산으로 구해낸다면 문제를 해결하기에 충분한 총 시간복잡도인 O(N^2) 알고리즘을 만들어 낼 수 있다..

 

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

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

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

	int N, bnd; cin >> N;
	if (N & 1) bnd = N / 2 + 1;
	else bnd = N / 2;

	ll ans = 0;
	for (int a = 1; a < bnd; a++) {
		for (int b = 1; b < bnd; b++) {
			int len = N - a - b;
			if (len < 2) continue;
			if (len < bnd) ans += len - 1;
			else ans += (bnd - 1) * 2 - (len - 1);
		}
	}

	cout << ans;
}