BOJ 11834 - 홀짝

 

이분 탐색 카테고리 문제만 연달아 풀다가 마주쳐서인지 쉽게 접근이 가능했지만 평소에 봤다면 꽤 힘들만했을 것 같다. 입력 값이 10^100인 걸 보면 어쨌건 시간복잡도가 log n이어야겠다 하는 게 이분 탐색과 연결 지을 힌트라면 힌트겠다. 그 외 숫자에 대한 접근은 간단하다.

 

짝수는 2의 배수이므로 홀수 -> 짝수 / 짝수 -> 홀수로 넘어가는 경우 모두 1만 더해주면 홀/짝이 바뀌게 된다. 반대로 짝수/홀수 상태가 유지돼야 할 때는 2씩 증가하면 된다. 값이 변하는 양은 정해져있고, 우리는 규칙만 찾으면 된다.

 

앞부분부터 하나씩 살펴보자.

먼저 초항에서 다음 항으로 넘어가는 부분이다. 홀 / 짝 / 홀 / 짝 순으로 나오는 수열이고, 초항이 홀수 1이므로 n = 2일때 올 숫자는 n = 1에서 1증가한 2가 된다.

 

n = 3인 경우, 문제에 따라 짝수가 2개 연달아 나와야 하므로 2가 증가한다.

홀수 1번, 짝수 2번이 왔으므로 이제는 홀수가 3번 와야할 차례다. n = 4로 갈 때 다시 1증가하며 5가 되고, 연달아 2씩 증가하며 홀수는 총 3번 등장한다.

 

 

이제는 규칙이 명확하게 보일 것이다. 모든 숫자는 기본적으로 2씩 증가하는데, 홀/짝이 바뀌는 부분에서만 2가 아닌 1이 증가한다. 결국 홀짝 수열의 n번 항이라는 건 2 * n의 숫자에서 1이 등장한 횟수만 빼주면 된다. 그리고 1이 등장하는 위치는 명확한 규칙에 따라 정해져있다.

 

2가 0번 등장했을 때 -> n이 1 증가했을 때

2가 1번 등장했을 때 -> n이 2 증가했을 때

2가 2번 등장했을 때 -> n이 3 증가했을 때

2가 3번 등장했을 때 -> n이 4 증가했을 때

...

 

결국 1~n까지의 합 공식을 통해 1이 몇 번 등장하는지 알 수 있다. n을 문제에서 준 파라미터라고 하고, x가 우리가 찾아야 할 1의 등장 횟수라고 하면

위 조건을 만족하면 되고 여기서 2를 양쪽에 곱해주면 조건이 나온다.

 

위 식을 사용하려면 2n의 값이 10^100 * 2까지 등장하므로, 이분 탐색을 통해 위 조건을 만족하는 x를 찾을 것이다. 그렇게 나온 x를 2n에서 빼주기만 하면 된다.

 

import sys

input = sys.stdin.readline


def get_input():
    return int(input())


def solution(n):
    # 1씩 증가한 횟수 세기
    target = 2 * n
	
    def get_cnt(mid):
        return mid * mid + mid

    def binary_search():
        left = 0
        right = (10**100) * 2

        while left < right:
            mid = (left + right) // 2

            if get_cnt(mid) < target:
                left = mid + 1
            else:
                right = mid

        return left

    return target - binary_search()


print(solution(get_input()))

 

비슷한 유형의 문제를 연달아 푸느라 나름 빠르게 풀 수 있었지만... 미래의 나는 어떻게 될지 모르기 때문에 기록을 남겨놓는다. 사실 포스팅 하면서도 공식을 왜 저렇게 사용했더라 싶어서 노트를 뒤적거렸다. 풀고 복습하는 것만이 살 길이다.