백준 2292: 벌집 (C)

문제

---

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

입력

---

첫째 줄에 N(1 ≤ N ≤ 1,000,000,000)이 주어진다.

출력

---

입력으로 주어진 방까지 최소 개수의 방을 지나서 갈 때 몇 개의 방을 지나는지 출력한다.

풀이

---

미리 설명하건대 나는 아주 복잡하고 이상한 방법으로 풀었다.
구글에 검색하면 더 현명한 풀이들이 많이 나온다.
어쩌다 이곳에 당도하였다면 이 풀이는 참고만 하고 다른 풀이로 푸는 것을 추천한다....

1. 정답 (최소 개수의 방을 지나서 갈때 지나는 방의 수)이 동일한 방의 번호들을 센다.
   사진처럼 1, 2~7, 8~19, 20~37, ... 이 된다.
2. 큰 쪽의 경계값 (1, 7, 19, 37, ...)은 모두 임의의 0보다 크거나 같은 정수 x에 대해 6*x+1이라는 공통점이 있다.
3. x는 0, 1, 3, 6, 10, ... 으로 증가한다: Xn=Xn-1 + n-1이라는 점화식을 갖는다.
4. 문제에서 주어지는 수 N으로 x를 찾으면, x를 활용해서 정답을 구할 수 있다.
   예를 들어, X = 3이라면, 0+1+2 = 3이므로,
   (for (i=0; i<X; i++)에서 i=2) 찾고자 하는 정답은 3 (i+1)이다.

• N으로 x 찾기:
  • N <= 6x + 1을 x를 기준으로 정리하면: x>=(N-1)/6이 된다.
  • N을 알고 있으므로 이 식을 만족하는 가장 작은 x를 찾는다.
  • 왜 가장 작은 x를 찾아야 하는가: 그냥 감으로 찍었음. 저도 정확히 설명 못함...

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main(void) {
  int N;
  float x;
  int result = 0;
  int i = 0;
  scanf("%d", &N);

  if (N == 1) {
    printf("%d", 1);
  } else {
    x = (N - 1) / 6.0;
    while (result < x) {
      result += i;
      i++;
    }
    printf("%d", i);
  }

  return 0;
}