취미로 코딩하기

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

이번에 볼 문제는 백준 2097번 문제인 조약돌이다.
문제는 아래 링크를 확인하자.

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

각 변의 길이가 정수이고 둘레가 일정한 직사각형은 모든 변의 길이의 차이가 최소화될 때 포함하는 격자점의 수가 최대가 된다는 사실은 잘 알려져있다.

위 사실을 이용해 직사각형의 x축 방향 길이와 y축 방향의 길이를 1부터 시작해 번갈아가며 1씩 늘리면서 N개의 격자점을 포함하기 시작하는 순간을 찾아내 문제를 해결할 수 있다.

위와 같이 길이를 늘려나갈 경우 직사각형이 포함하는 점의 개수는 변의 길이를 늘린 횟수의 제곱에 비례하므로 이 방법으로 문제를 해결하는 알고리즘은 $O(\sqrt{N})$에 동작한다.

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

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

ll N;
ll x = 1, y = 1;

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

	cin >> N;
	while (1) {
		if ((x + 1) * (y + 1) >= N) break;
		x++;
		if ((x + 1) * (y + 1) >= N) break;
		y++;
	}

	cout << (x + y) * 2;
}