PS 일지 (2024.03.22)

알고리즘 문제풀이 동아리 NPC 활동을 다시 시작했다.

고급반 사람들이 다들 잘해서 재미있을 것 같다.

C. 돌 가져가기

아무도 안 풀었길래 건들였는데, 가장 쉬운 문제였던 것 같다.

다음과 같은 입력이 주어진다.

8
WBBWBWBB
6 4 8 2 5 3 1 5

이는 공이 총 8개 있다는 의미이고, 각각의 공은 순서대로 WBBWBWBB 색으로 칠해져 있다는 것, 그리고 각각의 공의 무게는 6,4,8,2,5,3,1,5로 주어진다는 의미이다.

W	B	B	W	B	W	B	B
6	4	8	2	5	3	1	5

공은 하나씩 가져갈 수 있는데, 양쪽의 공의 색깔이 본인과 다를 때, 해당 공의 무게만큼 점수를 얻는다.

문제 변형

W B B W
6 4 8 2

이렇게 주어졌다고 해보자. 이때 우리는 중간에 끼인 검은색 공 둘 중 하나의 점수만 얻을 수 있다는 사실을 얻을 수 있다.

그러므로 위 입력 예시는 아래와 같이 생각할 수 있다.

W	B	W	B	W	B
6	8	2	5	3	5

이때, 혹자는 이렇게 하면 뺄 수 있는 공을 못빼는 경우도 생기지 않냐고 반박할 수 있다.

일단은 이런 의문을 기억해두고 풀이를 시작해보자.

풀이

위와 같은 경우에서 제일 오른쪽 공과 제일 왼쪽 공의 점수는 못 얻는다는 게 문제의 조건이기 때문에 결국 점수를 얻을 수 있는 후보는 아래처럼 좁아진다.

B	W	B	W
8	2	5	3

이때, 검은 공 두 개를 제거하면 간단히 최댓값 13을 얻을 수 있다.

W	B	W	B	W	B	W	B	W
1	9	1	9	1	9	1	9	1

이 경우엔 검정색 돌만 하나씩 전부 빼면 최대 점수 36을 얻을 수 있을 것이다.

하지만 이렇게 이쁘게 나오지 않는다면 어떨까?

W	B	W	B	W	B	W	B	W
1	9	9	9	9	1	1	1	1

이 경우에서도 최대점수 36점을 얻을 수 있을까?

얻을 수 있다.

5번째 흰색공(9)를 제거하면,

W	B	W	B	B	W	B	W
1	9	9	9	1	1	1	1

이렇게 나오게 될 것이고, 4번째 검정색 공을 빼기 전 5번째 검정색 공을 먼저 뺀다면 4번째 공의 점수(9)도 얻을 수 있다. 같은 방법을 반복하면 9 네 개의 점수를 모두 얻을 수 있다.

그럼 이렇게 가설 명제를 세워보자.

문제 변형을 완료한 이후에 (BBB와 같이 연속된 공을 하나로 합친 이후에) 수열의 길이가 $N$이라면,
양쪽 끝을 제외한 $N-2$개 중에서 큰 순서대로 절반의 개수($\lceil\frac{N-2}{2}\rceil$)를 더한 값이 정답이 된다.

1. $N=2$

• $N=2$ 일 때는 양쪽 돌 모두에게서 점수를 얻을 수 없으므로 자명하게 성립한다.

2. $N=3$

• $N=3$ 일 때는 가운데 돌만 색이 다를 것이므로, 이 돌에서만 점수를 얻을 수 있고 $\lceil\frac{N-2}{2}\rceil = 1$ 이므로 이 역시 성립한다.

3. $N\geq 4$

• $N\geq 4$일때는 가운데 끼어있으면서 점수를 얻을 수 없는 돌이 존재한다.

  여기서 점수를 얻어야 하는 돌은 $\lceil\frac{N-2}{2}\rceil$개에 포함되는 돌, 점수를 얻을 수 없는 돌은 $\lceil\frac{N-2}{2}\rceil$에 포함되지 않는 돌로 정의하자.

• 따라서 가운데 끼어있으면서 점수를 얻어야 하며, 양쪽의 돌 중 하나가 점수를 얻을 수 없는 돌이며,
  양 끝 돌도 아닌 돌 $S_i$가 존재할 수밖에 없다. ($i \neq 0 \;\;\&\;\; i\neq N-1$)

• 이때 $S_i$ 옆에 있는 점수를 얻지 않아야 하는 돌을 $S_{i+\epsilon}, \epsilon=1 \;\;\text{or} -1$이라고 하자.

  만약 $S_i$가 존재하지 않는다면, 중간에 끼어있는 모든 돌($N-2$개)로부터 점수를 얻을 수 있다는 말과 같고, 이는 문제 조건에 의해 불가능함이 자명하다.

• 이때 가장 먼저 $S_i$를 제거하고, 그 다음 $S_{i+\epsilon}$을 제거하자. 그러면 상황은 $N-2$인 것과 같다.

결론

• $N=2$인 상황과 $N=3$인 상황에서 이 명제가 성립하므로, 수학적 귀납법에 의하여 $N\geq2$에 대하여 모든 $N$에 대해 성립한다.

$1 \le N \le 3 \times 10^5$ 이고, 해당 문제를 푸는 과정에서 정렬에 $O(N\log N)$이 소요되므로 제한 시간 내에 해결할 수 있다.

다시 의문점으로 돌아와서

W B B W
6 4 8 2

이렇게 주어졌다고 해보자. 이때 우리는 중간에 끼인 검은색 공 둘 중 하나의 점수만 얻을 수 있다는 사실을 얻을 수 있다.

그러므로 위 입력 예시는 아래와 같이 생각할 수 있다.

W	B	W	B	W	B
6	8	2	5	3	5

이때, 혹자는 이렇게 하면 뺄 수 있는 공을 못빼는 경우도 생기지 않냐고 반박할 수 있다.

자 그렇다면, 이렇게 같은 색끼리 하나의 공으로 합치지 않았다고 가정했을 때 $\lceil\frac{N-2}{2}\rceil$개보다 더 많은 공을 뺄 수 있다는 말과 같다.

이게 가능할까?

일단 다시 원래의 모양으로 되돌아가서 생각해보자.

W	B	B	W	B	W	B	B
6	4	8	2	5	3	1	5

여기에서 세 번째 B를 얻기 위해 우리는 네번째 W를 희생시켰고, 만약 $\lceil\frac{N-2}{2}\rceil$개보다 더 많은 공을 뺄 수 있다면, 그 후보는 네번째 W가 될것이다. 얼핏 보면 가능할 것 처럼 보이기 때문이다.

그러나 세번째 B의 점수를 얻기 위해서는, 문제 조건에 명시되어 있다시피 양쪽이 모두 W이어야 하므로, 무조건 양쪽에는 B가 없어야 하며, 이를 위해 본인을 제외한 모든 B를 먼저 제거해야 한다.

반면, 네 번째 W의 점수를 얻기 위해서는 왼쪽에 무조건 B가 있어야 할 것이다.

세 번째 B를 얻을 것인지, 네 번째 W를 얻을 것인지 골라야 하는 문제가 생겨버린다.

즉 연속된 같은 색을 하나로 합치는 의미는 $\lceil\frac{N-2}{2}\rceil$개라는 것에 어떠한 영향을 끼칠 수 없다는 것이다.

따라서 이런 가정을 들어 문제를 풀어도 상관없다.