2020. 2. 17. 22:38ㆍ백준 알고리즘 단계별/수학 1 단계
백준 BOJ C# 2292 벌집
출제 링크 : https://www.acmicpc.net/problem/2292
2292번: 벌집
위의 그림과 같이 육각형으로 이루어진 벌집이 있다. 그림에서 보는 바와 같이 중앙의 방 1부터 시작해서 이웃하는 방에 돌아가면서 1씩 증가하는 번호를 주소로 매길 수 있다. 숫자 N이 주어졌을 때, 벌집의 중앙 1에서 N번 방까지 최소 개수의 방을 지나서 갈 때 몇 개의 방을 지나가는지(시작과 끝을 포함하여)를 계산하는 프로그램을 작성하시오. 예를 들면, 13까지는 3개, 58까지는 5개를 지난다.
www.acmicpc.net
접근 방법
문제에 관해서 서칭하던중
https://en.wikipedia.org/wiki/Centered_hexagonal_number
Centered hexagonal number - Wikipedia
A centered hexagonal number, or hex number,[1] is a centered figurate number that represents a hexagon with a dot in the center and all other dots surrounding the center dot in a hexagonal lattice. Centered hexagonal numbers have practical applications in
en.wikipedia.org
이미 유명한 도형? 인지 이름까지 있었다. 중심있는 육각수 ? 라고 하는데
문서에는 각 방의 수를 구하는 공식 또한 나와있었다.
문제에서 주어진 13을 넣고 계산해보면
2를 출력하는데 아마 첫째 방 포함시켜야 해서 +1 로 카운트 해주면 될꺼같다.
혹시 몰라서 주어진 58 또한 계산해 봤다.
내 생각이 맞는거 같다. 이제 저 공식으로 코드를 구성해준다.
하지만.. 런타임 에러가 생겼는데 아마 문제에 주어진 1,000,000,000 번 작동하는 경우 때문인거 같다.
수학 단계는 직접 계산하는 부분이 있으면 런타임 에러가 자주 발생한다.
예외를 처리하거나 if문이나 특정 제약을 둬서 증가,감소를 지켜주는 방향으로 코드를 짜야했다.
우선 소스를 더 찾아봤다.
대부분 범위, 배수, 몇 겹인지를 나누어서 증감 되는 형태를 가지고 있었다.
즉, 6씩 증가하는 계차수열을 이용하여 문제를 푸는게 핵심이였다.
코드