[Python] 11834번 홀짝

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

---

 

25/06/15

 

 

이전에 북마크 해두었던 문제로, 몇 개를 좀 나열해보다가 쉽게 해결할 수 있었다.

---

 

문제 접근 방식:

 

 

어떤 수열이 다음과 같은 규칙으로 주어진다.

 

홀수 $1$개, 짝수 $2$개, 홀수 $3$개, ... 이런 식으로 연속된 홀수와 짝수가 개수를 점점 늘려가며 늘어난다.

 

즉, $1 \ \ 2 \ 4 \ \ 5 \ 7 \ 9 \ \ 10 \ 12 \ 14 \ 16 \ \ \cdots$으로 이루어져있다.

 

이때 우리가 구하고자 하는 것은 이 수열의 $N$번째 항을 구하고 싶다. $N$의 제한이 $10^{100}$이므로, 당연히 시뮬레이션으로 구하면 터진다는 것을 확인할 수 있다.

 

따라서 우리는 $N$번째 항을 "이분 탐색"으로 구해볼 생각을 할 필요가 있다. (혹은 일반항을 구하거나)

 

처음 접근한 방법은 일반항을 구하는 것이었는데, 이건 실패했다. 그래서 이분 탐색으로 방향을 틀었다.

 

먼저 늘어나는 양을 관찰함으로써 규칙을 찾아보고자 했다.

 

$+1, +2, +1, +2, +2, +1, +2, +2, +2, +1, \cdots$처럼 늘어나는 양이 $1$과 $2$가 교대해가며, $2$가 $1$개 씩 더 많이 늘어남을 확인할 수 있다.

 

이를 통해 거꾸로 생각한다면 $+2$만 늘어나는데, 거기에 중간중간 $-1$이 있다고 "역으로"생각할 수 있다.

 

다시 말하자면, 수열에서 이웃하는 두 항 사이의 차이가 $+1$과 $+2$로 구성되어있으나, $+2$으로만 이루어져있다고 생각하고, $+1$로 구성되어있는 것은 $-1$이 추가적으로 더해져있다고 생각하는 것이다.

 

예를 들어, $+1, +2, +1, +2, +2, +1, +2, +2, +2, +1, \cdots$은 아래와 같이 2개로 분리할 수 있다.

$$+2, +2, +2, +2, +2, +2, +2, +2, +2, +2, \cdots$$

$$-1, +0, -1, +0, +0, -1, +0, +0, +0, -1, \cdots$$

 

따라서, 등차수열 공식을 통해 나온 수에서 몇번 만큼 $1$이 빠졌는가를 세어주면 충분하다.

 

공차가 $2$이고 초항이 $1$인 일반항의 공식은 $a_n = 2n - 1$이다.

 

따라서 $N$번째 원소는 $2N - 1$에서 $1$이 일정 수준 빠진 것과 같다.

 

잘 보면 $-1$이 놓인 규칙이 $1, 2, 3, ...$과 같이 증가한다.

 

초기 항에서 $-1$이 더해진 횟수는 $N$이 아니라 $N-1$을 기준으로 따져줘야한다. 따라서, $N-1$보다 작거나 같으면서 가장 큰 $k(k+1)/2$에 해당하는 $k$를 찾고, 그 $k$번 만큼 $1$이 빠짐을 확인할 수 있다.

 

따라서, 다음과 같은 최종 식을 확인할 수 있다.

 

$$a_n = 1 + 2(n-1)  - k$$

 

해당되는 $k$의 값은 이분 탐색으로 찾아주면 충분하다.

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 11834번 홀짝
# 수학, 이분 탐색
'''
접근 방법:
1,2,4,5,7,9,10,12,14,16,17
+1,+2,+1,+2,+2,+1,+2,+2,+2,+1,+2,+2,+2,+2,+1...
2, 4, 7, 11, 16
1, 3, 6, 10, 15
N번째 원소 -> N-1번째를 따져줌.
N-1보다 작거나 같으면서 가장 큰 k(k+1)//2에 해당하는 k찾기
-> k번만큼 1이 빠짐.
-> 1 + 2*(N-1) - k가 N번째 원소가 된다.
'''
import sys
input = sys.stdin.readline

N = int(input())
m, M = 0, 10**50
while m+1 < M:
    k = (m+M)//2
    if N-1 >= k*(k+1)//2:
        m = k
    else:
        M = k
print(1 + 2*(N-1) - m)