[백준] 24979 COW Operations

오랜만에 문제풀이 글

 

지난 주, 학회 연습셋에 쓸 문제가 마땅치 않아 USACO 문제를 두 개 넣었었고, 그 중 하나이다.

나는 이 문제가 굉장히 까다롭다고 생각했다. 그리고 풀이 세션할 때 질문이 많이 들어올 줄 알고, 연습셋 때 풀이를 열심히 준비했었다. 근데, 다들 잘 풀더라... 질문도 없었다. 아쉬워서 글로 남겨본다.

 

boj.kr/24979

문제를 요약하면 다음과 같다.

C는 OW 혹은 WO로 바꿀 수 있다.

O는 CW 혹은 WC로 바꿀 수 있다.

W는 CO 혹은 OC로 바꿀 수 있다.

인접한 두 문자가 같으면 두 문자를 삭제할 수 있다.

 

이제 쿼리 [l, r]이 들어온다.

구간 [l, r]에 위 연산을 원하는만큼 적용해서 s[l..r]을 "C"로 만들 수 있는지 묻는 문제이다.

 

---

 

코드포스 같은 곳에서 이런 문제를 보면 꼭 연산 몇 개를 합쳐서 더 쉬운 연산 하나를 생각해 내더라. 암튼 그런 점을 염두해 두고 혹시 그런 연산들이 있는지 간단히 살펴보았는데, 아래와 같은 특징을 얻었다.

 

1.

CO는 W로 바꿀 수 있다. (CO->CCW->W)

마찬가지로 아래도 성립한다.

OW는 C로 바꿀 수 있다.

CW는 O로 바꿀 수 있다.

 

그러므로 우리는

C <-> (OW or WO)

O <-> (CW or WC)

W <-> (CO or OC)가 자유롭다.

 

2.

1.을 이용하면 다음 두 사실을 얻을 수 있다.

 

C와 O는 자리를 바꿀 수 있다.

O와 W는 자리를 바꿀 수 있다.

즉, CO <-> OC와 OW <-> WO가 자유롭다. 

 

이는 생각보다 어렵지 않게 알 수 있다.

CO->CCW->W->OC와 같이 하면 된다. 반대도 똑같다.

 

 

3.

이제 문제의 목표를 생각해보자. 우리는 C만 남겨야 한다. 그런데 위의 특징들을 살펴보면 W는 C와 거리가 먼 것 같다. 그러니까 W를 먼저 없애고 생각해보자.

즉, 모두 OC로 바꾸어주자. (참고로 CO로 바꿔도 똑같다. OC<->CO이니까... )

 

그럼이제 우리가 보는 문자열은 C와 O로만 이루어져 있다. C와 O는 자리를 바꿀 수 있기 때문에, 우리가 보는 문자열을 CCCCCCC...OOOOO와 같은 형식으로 바꿀 수 있다.

 

 

4.

그렇다면 CCCCCC....OOOOOO와 같은 문자열에서 C의 개수가 홀수, O의 개수가 짝수면 O를 모두 삭제하고 C도 1개 빼고 다 삭제하면 C 한 개만 남게 된다.

 

즉, 주어진 구간의 W를 모두 CO로 바꾸었을 때, C가 홀수 개, O가 짝수 개 있으면 주어진 구간을 "C"로 바꿀 수 있다. 

구간의 C, O, W의 개수는 누적합 전처리를 통해 O(1)에 구할 수 있다.

 

 

 

 

 

재미있고 어려운 문제라고 생각한다....