이 글의 목적?

분명 이전에 풀어봤었고 정리도 한적이 있던 문제임에도 '아~ 이거 예전에 풀어봤던건데~'라는 감상평만 떠오를 뿐이었다. 코드없이 어떻게 풀었는지에 대해서만 적어보자. (한 번 정리해도 안되면 두 번 정리하자는 마인드!)

문제

위의 그림과 같이 육각형으로 이루어진 벌집이 있다. 그림에서 보는 바와 같이 중앙의 방 1부터 시작해서 이웃하는 방에 돌아가면서 1씩 증가하는 번호를 주소로 매길 수 있다. 숫자 N이 주어졌을 때, 벌집의 중앙 1에서 N번 방까지 최소 개수의 방을 지나서 갈 때 몇 개의 방을 지나가는지(시작과 끝을 포함하여)를 계산하는 프로그램을 작성하시오. 예를 들면, 13까지는 3개, 58까지는 5개를 지난다.

풀이

접근 방법은 공식화다. 하단의 이미지처럼 1에서 각 색상까지의 거리는 하나씩 증가한다.

• 1 까지 거리 0
• 2 ~ 7 까지 거리 1
• 8 ~ 19 까지 거리 2
• 20 ~ 37 까지 거리 3
• ...

그 다음으로는 범위에 어떤 규칙을 가지는지 확인해보자.

• 시작점은 1, 2, 8, 20
• 끝점은 1, 7, 19, 37

6의 배수로 증가하는 것을 확인할 수 있다. 이 내용을 공식화해보자.

• f(1) = 1
• f(2) = f(1) + 6 x 1 = 7
• f(3) = f(2) + 6 x 2 = 19
• f(4) = f(3) + 6 x 3 = 37
• f(n) = f(n-1) + 6 x (n-1)

여기서부터는 간단하다. 각 범위별로 점수가 하나씩 올라간다는 점을 생각하면서 구현해주면 된다.

이 글의 레퍼런스

• 없음