백준 11834 홀짝

문제

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

 

풀이

짝수와 홀수가 반복되는 것을 하나로 묶고 각각의 그룹을 레이어라 하자.

레이어1: 1

레이어2: 2 4

레이어3: 5 7 9

...

문제의 정의대로 각 레이어에 공차가 2인 등차 수열이 들어있다.

레이어 i와 i+1의 관계를 알아보자.

레이어 i의 시작을 s(i), 레이어 i+1의 시작을 s(i+1)라고 하자.

해당 관계가 성립한다.

s(i) + 2*(i-1) + 1 = s(i) + 2i - 1 = s(i+1)

따라서 s(i+1) - s(i) = 2i - 1

그럼 각 레이어의 시작을 구할 수 있다.

s(1) = 1

s(i) = s(1) + (1 + 3 + 5 + ... + 2(i-1)-1) = 1 + (i-1)^2

N이 어떤 레이어 L에 속하는지 알려면, 레이어의 크기는 i가 증가될 때 마다 1씩 증가하므로

1 + 2 + 3 + ... L + 1 = (L+1)(L+2)/2 >= N 을 만족하는 L을 구하면 된다.

이는 큰 수 연산이 지원되는 언어에서 이분 탐색을 이용해 구할 수 있다.

 

이제 N이 어떤 레이어에 속하는지 알았으므로 N이 레이어에서 몇번째인지 구해야한다.

L(L+1)/2번째가 레이어의 시작 인덱스이다.

따라서 N - L(L+1)/2를 하면 구할 수 있다.

각 레이어는 공차가 2인 등차 수열이므로 s(L) + (N - L(L+1)/2 - 1) * 2 = 1 + (L-1)^2 + (N - L(L+1)/2 - 1)*2를 하면 원하는 답을 얻을 수 있다.