[C] 2292: 벌집

계차수열을 이용하여 수식을 구해서 풀 수 있다

거리가 1인 벌집은 1

거리가 2인 벌집은 2~7

거리가 3인 벌집은 8~19

거리가 4인 벌집은 20~37..

이런 식으로 진행되기 때문에 거리가 n일때 벌집은 f(n-1)~f(n)까지 일 것이다

맨 끝 벌집이 1->7->19->37->61..로 증가하고 

각 끝 벌집끼리는 6->12->18->...로 증가하는 것을 알 수 있다.

따라서 계차수열을 이용하면 f(n)=3*n^2-3*n+1인 것을 알 수 있다.

이를 이용해 문제를 풀게 되면 아래와 같다.

#include <stdio.h>

int main(void)
{
 int n;
  scanf("%d",&n);
  int i;
  for(i=1;i<100000;i++) //수식에 10^5를 넣으면 대략 10^10까지 가능하므로 입력 범위 커버 가능
    {
      int k=3*i*i-3*i+1; //계차수열을 이용한 수식 (1->7->19->37..)
      if(k>=n) //입력받은 수가 거리보다 작을때 멈춤
        break;
    }
  printf("%d",i);

  return 0;
 
}

계차수열을 알고 있지 않다면 f(n)을 유도하지 않고 아래와 같이 쓸 수 있다.

#include <stdio.h>

int main(void) {
	int n;
	scanf("%d", &n);

	int cnt = 1;
	int max = 1;
	int add = 6;

	while (1) {
		if (n <= max)
        break;
        
		max += add;
		add += 6;
		cnt++;	
        }

	printf("%d\n", cnt);
	return 0;
}