[Baekjoon - 21605] 아름다운 수열

난이도: Silver I

 

태그

• Constructive

 

풀이

1. 얻을 수 있는 최고점은 몇 점일까?

사용되는 수가 +1과 -1 뿐이고, 수에 -1이 곱해질 수도 있으니 각 \( B_i \)의 최고점과 최저점을 같이 계산해봅시다.

 

\( B_0 \)은 정의상 0점입니다.

\( B_1 \)은 \( \pm B_0 \pm 1 = 0 \pm 1 \)이므로, 최소 -1점, 최대 +1점이 됩니다.

\( B_2 \)는 \( \pm B_1 \pm 1 = \pm 1 \pm 1 \)이므로, 최소 -2점, 최대 +2점이 됩니다.

...

 

이런 식으로 규칙을 따르다 보면, \( B_N \)은 최소 \( -N \)점, 최대 \( +N \)점이 되는 것을 볼 수 있습니다.

// 엄밀한 증명은 수학적 귀납법을 사용합니다. 흐름은 비슷하므로 생략합니다.

 

2. [1]에서 찾은 점수를 만들어보자.

\( |B_{N-1}| \le N-1 \)이므로, \( B_N = N \)이 되게 만들기 위해서는 \( B_N = -B_{N-1} + 1 \) 또는 \( B_N = B_{N-1} + 1 \)이 되어야 합니다.

 

+1과 -1의 균형을 맞춰야 하므로, 이 중 \( B_N = -B_{N-1} + 1 \)를 선택해봅시다.

이제 \( B_{N-1} = -(N-1) \)을 만들어내기만 하면 됩니다.

 

이도 어렵지 않은데, \( B_i = +B_{i-1} - 1 \text{ for all } i < N \)으로 잡으면, \( B_{N-1} = -(N-1) \)을 간단히 만들어낼 수 있습니다.

 

모든 위치에서 +1과 -1이 하나씩 쓰였으니 개수 조건은 자명히 만족합니다.

 

3. 코드