[파이썬/python] 백준 - 31778 PPC 만들기

문제

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

---

문제 설명

1. 문자열 S는 길이가 N이며 알파벳 대문자 C와 P만으로 이루어져 있는 문자열이다.
2. 대회 전 문자열 S에 다음과 같은 연산을 최대 K번 시행할 수 있다.
   1.  1 ≤ i ≤ j ≤ N인 두 정수 $i, j$를 골라  $S_i$ 와  $S_j$를 바꾼다.
3. 완성된 문자열 S에 PPC 부분문자열이 가장 많도록 하고 싶다.
   1. PPC 부분 문자열이란, 1 ≤ i ≤ j ≤k ≤N 이고 $S_i = S_j = P, S_k = C$인 $(i,j,k)$를 의미한다.
4. 만들 수 있는 PPC 부분문자열의 개수의 최댓값을 구한다.

 

---

풀이

먼저 K번 시행할 수 있는 연산을 통해 최대한 많은 PPC를 만들 수 있는 문자열을 만들어야 한다.

 

결국 부분문자열은 연속적인 세 숫자가 P, P, C라는 수를 이루어야 한다.

그렇기에 C는 뒤로, P는 앞으로 옮기면 가장 많은 PPC를 만들 수 있을 것이라고 생각했다.

 

떠올린 방법은 투 포인터다.

s, e를 잡고 s의 값이 C, e의 값이 P라면 바꿔주도록 구현했다. 바꾸는 횟수가 k보다 커지게 되면 연산을 종료했다.

 

문제는 PPC 문자열을 어떻게 탐색할 것인가?이다.

 

처음에는 DP를 통해 문제를 해결할 수 있지 않을까라고 생각했다.

하지만 1차원 DP로는 해결이 불가능했고 2차원 DP로는 어떻게든 될 것 같았는데 시간복잡도가 너무 커서 문제의 조건에 맞지 않을 것이라고 생각했다.

 

다시 문제를 바라보고 문제에서 힌트를 얻었다.

 결국에는 PPC라는 부분문자열을 찾는 것 이기 때문에, 앞에서부터 순차적으로 탐색하면 가능하지 않을까?라는 생각이 문득 들었다.

 

근데 단순 완탐으로 하기에는 $N^3$이기 때문에 불가능하다.

 

떠올린 방법은 조합이었다.

사실상 이 문제는 연속적으로 PPC가 나오는 것이 중요하기 때문에 뒤에서 C가 나왔을 때 앞에서 만들 수 있는 경우의 수를 모두 더해주기만 하면 되는 것이다.

누적합으로 풀 수 있다고도 생각했는데 같은 방식인 것 같다.

 

예제 2번을 K번의 연산을 진행해서 정리하면 아래와 같은 문자열을 얻을 수 있다.

각 위치에서 만들 수 있는 PP의 조합 개수를 구해보자. 

P	P	P	C	P	C	C	C
0	1	3	3	6	6	6	6

PP의 조합은 사실상 N개의 P 중에서 2개를 선택하기 때문에 $n(n-1) / 2$ 수식을 통해 $O(1)$로 연산이 가능하다.

 

그렇기 때문에 P의 개수를 누적하면서 조합을 더해가면 C가 나온 위치의 조합 개수가 PPC 부분문자열의 개수인 것이다.

 

즉 모든 PPC 조합을 더해주면 3 + 6 + 6 + 6 = 21이다.

 

문제가 직관적이라 어렵지 않게 풀 수 있었다.

 

 

 

 

---

코드

import sys
input = sys.stdin.readline

n,k = map(int,input().split())
S = list(input().strip())

s,e = 0, n-1

while s < e and k > 0:
    if S[s] == 'C':
        if S[e] == 'P':
            S[s], S[e] = S[e], S[s]
            s += 1
            e -= 1
            k -= 1
        else:
            e -= 1
    else:
        s += 1

def cal_cost(p):
    return (p*(p-1)) // 2

cnt = 0
res = 0
for i in range(n):
    if S[i] == 'P':
        cnt += 1
    elif S[i] == 'C':
        res += cal_cost(cnt)

print(res)

---

시간복잡도

• 최대 K번의 연산을 진행한다고 가정했을 때, 두 문자열을 바꾸는 연산은 총 $O(K)$만큼 반복된다.
• 부분 문자열 PPC를 찾을 때 $O(N)$만큼 반복된다.
• 즉 시간복잡도의 총합은 $O(K) + O(N)$, 약 $O(N)$정도의 시간복잡도를 예상해 볼 수 있겠다.
• $N = 10^5, K = 10^5 -1 $