[정올 1057] 미친 수열

http://jungol.co.kr/bbs/board.php?bo_table=pbank&code=1057&sca=99 

JUNGOL

#include <stdio.h>
#include <math.h>
long long int n;

void get_ans(void)
{
	long long ans = (long long)(-1 + sqrt(1.0 + 8 * n)) / 2;	//근의 공식
	if ((ans * (ans + 1) / 2) < n) printf("%lld", ans + 1);		//출력 시 타입 주의
	else printf("%lld", ans);
}

int main(void)
{
	scanf("%lld", &n);	//input시 타입 주의
	get_ans();
	return 0;
}

다시 풀어도 그지같은 문제라고 할 수 있겠다. 아.. C언어 진짜 타입 킹받아....

 

 

일단 1, 2, 2, 3, 3, 3, 4, 4, 4, 4, ... 이 무친 수열의 규칙은 다음과 같다.

일반화를 못하겠어서 예를 들자면, 숫자 3으로 이루어진 수열군의 마지막 항의 번호는  1 + 2 + 3 = 6 이다. 그 이유는, 숫자 1이 1개 / 숫자 2가 2개 / 숫자 3이 3개로 이루어져 있기 때문이다. 

따라서 숫자 k로 이루어진 군수열의 마지막 항의 번호는 1 + 2 + 3 + ... + k 일 것이다.  그 이유는 위와 마찬가지로 숫자 1이 1개 / 숫자 2가 2개 / 숫자 3이 3개 / ... / 숫자 k가 k개로 이루어져 있기 때문이다. 

 

문제에서 주어진 것이 항의 번호 n이므로, 위의 로직에 의해 등차수열의 합 공식을 적용하면 k * (k + 1) / 2 = n이 되어야 한다. 

따라서 이 문제에서는 이차 방정식의 해인 k를 구하면 된다. 

 

여러 방법이 있겠지만, n의 범위가 몹시 크기 때문에 루프를 돌리지 않고 수학적으로 계산해 주었다. 

근의 공식을 활용하여 ans 를 구하고, 그 타입을 long long으로 변환한다. 

다음으로 도출한 ans를 활용하여 k * (k + 1) / 2를 다시 구해보고, 그 값이 n보다 작으면 끝 항은 아니지만 해당 수열군의 숫자이므로 ans + 1을 해준다.