BOJ 11834 홀짝

https://www.acmicpc.net/problem/11834

11834번: 홀짝

 

n번째 수가 몇번 째 그룹(몇번째 홀수 그룹, 몇번째 짝수 그룹)에 속하는지 구한다면 풀 수 있는 문제이다.

나는 다음과 같은 식을 세워서 풀었다

$$  \frac{i^2 + i}{2} < n <= \frac{i^2+3*i+2}{2}   $$

sqrt함수는 정밀도 때문에 사용하지 못해, 이진탐색을 이용해 i를 찾아 풀었다.
또한 100자리 수가 필요했기 때문에 big integer를 언어 차원에서 지원하는 python을 이용하여 풀었다.

a = int(input())
answer = 1

x = 10**100
y = 0
while x > y:
    b = (x+y) // 2
    if b*b + b >= 2*a:
        x = b - 1
    elif b*b + 3*b + 2 < 2*a:
        y = b + 1
    else:
        x = b
        break

x += 1
answer = 2*a - x
print(answer)