[BOJ 27246 // C++] Различные квадраты

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

 

이번에 볼 문제는 백준 27246번 문제인 Различные квадраты이다.
문제는 아래 링크를 확인하자.

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

27246번: Различные квадраты

주어진 n개의 단위 사각형으로 최대한 많은 종류의 사각형의 구성은(구성 가운데 하나는) 1, 4, 9와 같이 작은 제곱수넓이의 사각형부터 차례로 만들어나가는 전략으로 항상 구해낼 수 있다는 것을 관찰하자.

 

1부터 k까지의 모든 제곱수의 합은 \(\frac{k(k+1)(2k+1)}{6}\)와 같이 구할 수 있음을 이용해 이진탐색으로 문제를 해결하자.

 

답의 크기가 충분히 작음(150만 이하)을 관찰한다면 직접 작은 크기의 사각형부터 구성해나가는 반복문 시뮬레이션으로도 문제를 충분히 해결할 수 있음을 알 수 있다.

 

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

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

ll N;

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

	cin >> N;

	ll L = 1, R = 1500000;
	while (L < R) {
		ll mid = (L + R) / 2 + 1;
		if (mid * (mid + 1) * (2 * mid + 1) / 6 > N) R = mid - 1;
		else L = mid;
	}

	cout << L;
}