[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. 코드