[BOJ 23890] 백준 23890번 - 달팽이팽이
GBS Coding Contest 2021 풀이 | ||
---|---|---|
A | [BOJ 23885] 비숍 투어 | |
B | [BOJ 23886] 알프수 | |
C | [BOJ 23887] 프린트 전달 | |
D | [BOJ 23888] 등차수열과 쿼리 | |
E | [BOJ 23889] 돌 굴러가유 | |
F | [BOJ 23890] 달팽이팽이 | |
G | [BOJ 23891] 타이어 끌기 | |
H | [BOJ 23892] 바코드 찢기 |
1. 문제
$23890$. 달팽이팽이 (GBS Coding Contest 2021 Open F번)
2. 풀이
축을 중심으로 판을 한 바퀴 돌리면, 빨간 실선을 반지름으로 하는 원이 그려진다. 따라서 빨간 실선의 길이가 가장 크도록 축을 잡으면 된다.
이때, 문제의 조건에 따라서 축은 판의 경계가 아닌 정확히 내부에 위치해야 하며, 축의 좌표는 $(x, y)$ 모두가 정수여야 한다. 빨간 실선의 길이는 축의 좌표가 $(a, b)$라고 했을 때, 그림에서 볼 수 있듯이 $L = \sqrt{a^2 + (b+R)^2}$이다.
전투력을 최대화하는 축 좌표가 여럿일 경우, $x$좌표가 가장 크며, $y$좌표가 가장 큰 답을 출력해야 한다. $x$좌표 하나에 $y$좌표는 1사분면(반원의 위쪽)과 4사분면(반원의 아래쪽) 두 경우가 나오는데, 여기서 $y$좌표 값이 커야 하기 때문에 반원의 위쪽만 생각하면 된다.
$L$ $=\sqrt{a^2+(b+R)^2}$ $=\sqrt{a^2+(\sqrt{R^2-a^2}+R)^2}$ $=\sqrt{a^2+R^2-a^2+2R\sqrt{R^2-a^2}+R^2}$ $=\sqrt{2R^2+2R\sqrt{R^2-a^2}}$
따라서, $L$의 길이는 $a$가 증가할수록 줄어드므로, $b$를 $R-1$로 잡고 $a^2+b^2$이 최대한 $R$과 가깝게 $a$를 두면 된다.
$y$ $=R-1$로 두면, $x$ $=\sqrt{R^2-y^2}$ $=\sqrt{R^2-(R-1)^2}$ $=\sqrt{2R-1}$ 이 된다. 단, 축은 판의 경계가 아니어야 하므로 $a^2+b^2$이 정확히 $R$이 되면 안 된다.
만약 정확히 $R$이라면, $y$좌표는 그대로 두고 $x$좌표를 $-1$하면 된다. (정확히 $R$이 되는 경우는 $R$이 $5$일 때부터 이므로, $x$좌표를 $-1$한다고 해서 경계에 도달할 일은 없다.)
3. 채점 결과
4. 회고
.
댓글남기기