벌집의 위치에 따라 중앙으로부터 얼마나 떨어져있는지 구하는 문제입니다. 1의 경우는 정중앙이므로 거리가 1, 2~7은 거리가 2, 3~19는 거리가 3, …입니다. 이것의 규칙을 찾으면 쉽게 풀 수 있습니다. 이 문제는 삼각수와 관련이 있는데, 주소에서 4를 더한 값을 6으로 나눈 몫을 보겠습니다.
| 주소 | (주소+4)을 6으로 나눈 몫 |
|---|---|
| 1 | 0 |
| 2~7 | 1 |
| 8~13 | 2 |
| … | … |
몫이 1인 곳은 거리가 2, 몫이 2 또는 3인 곳은 거리가 3, 몫이 4, 5, 6이면 4, 몫이 7, 8, 9, 10이면 5, …의 규칙이 생깁니다. 즉 n-1번째 삼각수보다 크고 n번쨰 삼각수보다 작거나 같은 몫을 가지면 답이 n이 되는 것이죠. 이제 이것을 함수로 만들어보겠습니다. 먼저 n번째 삼각수를 구하는 공식인 \(\frac{n(n+1)}{2}\)이 있을 때 n을 구하는 공식이 필요합니다.
\[S_n=\frac{n(n+1)}{2}\\ 8S_n=8\frac{n(n+1)}{2}=4n^2+4n\\ 8S_n+1=4n^2+4n+1=(2n+1)^2\\ \sqrt{8S_n+1}=2n+1\\ n=\frac{\sqrt{8S_n+1}-1}{2}\]만약 Sn 자리에 삼각수가 아닌 다른 수를, 예를 들어 n번째 삼각수와 n+1번째 삼각수 사이의 수를 집어넣으면 n과 n+1 사이의 실수가 나옵니다. 그런데 우리가 찾는 것은 n-1번째 삼각수보다 크고 n번째 삼각수보다 작거나 같은 몫을 가질 때 n을 반환하는 것이므로 위 식을 적용한 후 올림을 하면 되겠습니다. 이제 마지막으로 Sn 자리에 넣을 수는 위에서 구한 (주소+4)를 6으로 나눈 몫을 사용하면 답이 나올 것입니다. 이를 정리하여 답을 계산하면 됩니다.
사실 이 문제는 거리가 n인 점의 범위를 구하고 이 범위에 속하면 n을 출력하고 그게 아니면 n+1인 점의 범위를 구한 후 다시 비교하는 식의 반복문을 사용하는 것이 정석인 것 같습니다.
소스 코드
| 언어 | 코드 | 시간 |
|---|---|---|
| Python 3 | 코드(Github) / 코드(백준) | 2020-03-25 19:45:49 |