취미로 코딩하기

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

이번에 볼 문제는 백준 23890번 문제인 달팽이팽이이다.

문제는 아래 링크를 확인하자.

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

중심축은 반원 내부(경계 제외)에만 정할 수 있으므로, 달팽이팽이의 전투력이 최대가 되게 만들기 위해서는 반원 위의 가장 거리가 먼 점까지의 거리를 가장 크게 하는 중심축을 골라야한다. 그 거리를 반지름으로 하고 중심축을 중심으로 하는 원의 내부의 넓이가 달팽이팽이의 전투력이 되기 때문이다.

반원의 경계까지 중심축을 정할 수 있었다면, 반원 위의 가장 멀리 떨어진 두 쌍의 점은 지름의 양쪽 끝이므로 중심축을 지름의 한쪽 끝으로 정했을 것이다. 이에 착안하여, 문제에서 구하는 점은 지름의 한쪽 끝에서 1만큼 떨어진 y좌표와 그 y좌표에서 반원 내부의 최대한 y축과 떨어진 정수 x좌표를 갖는 점이 될 것임을 추측할 수 있다.

지름의 한쪽 끝에서 y좌표가 2 이상 떨어진 점에서의 반원 위 거리 최댓값은 2R-1을 넘을 수 없다는 것을 계산을 통해 증명하는 것으로 위의 추측을 정당화하고, 문제를 해결할 수 있다.

찾은 격자점이 반원의 경계에 있지는 않은지 주의하여 구현하자.

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

#include <iostream>
#include <cmath>
using namespace std;

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

	int R; cin >> R;
	int x = sqrt(2 * R - 1);
	if (x * x == 2 * R - 1) cout << x - 1 << ' ' << R - 1;
	else cout << x << ' ' << R - 1;
}