[Codeforces] 1694B. Paranoid String

이 문제는 greedy하게 풀면 모든 조합을 만들 필요가 없다고 한다..나는 모든 조합을 다 시도해봤더니 시간 초과가 발생한다.

 

We want to show that a binary string T of length $m$  is paranoid if and only if $m = 1$ or($m > 1$ and $S[m] \neq S[m - 1]$)

 

🌱 In the case of $S[m - 1] = S[m]$

우리는 마지막 두 char를 지울 수 없다.

왜냐하면 동일한 char라서 남아있기 때문이다.

따라서 S는 paranoid가 아니다.

 

🌱 In the case of $S[m - 1] \neq S[m]$

만약 $m = 2$이라면, 우리는 하나의 연산만으로 우리의 목표에 도달할 수 있다.

그렇지 않은 경우라면 만약 마지막 char가 0이라고 가정하자.

이렇게 되면 마지막 세 글자는 010 이거나 110이다.

010의 경우, $[S_{m-2}, S_{m-1}]$에 연산을 수행할 수 있다.

110의 경우, $[S_{m-1}, S_{m}]$에 연산을 수행할 수 있다.

 

그 결과 마지막 두 글자는 10이 되고, 우리는 $m = 1$이 될 때까지 이러한 알고리즘을 수행할 수 있다.

길이가 1인 paranoid의 부분 문자열 개수는 $n$과 동일하다. 더 긴 부분 문자열을 세기 위해서는 $r$을 인덱스 2부터 n까지 고정한다.

만약 $S[r] \neq S[r - 1]$에서는 우리는 answer에 $r - 1$을 더한다.

 

Complexity : $O(n)$

 

우선 작은 길이부터 다 도전해본다.

길이가 1인 경우는 0, 1

길이가 2인 경우는 01, 10

길이가 3인 경우는 110, 010, 101, 001 이 가능하다.

왜냐하면 규칙 자체가 뒤의 숫자가 남는 것이고, 마지막 숫자와 그 바로 직전 숫자가 다르면 둘 간의 연산을 하거나 앞선 숫자들을 연산한다.

그렇게 일일이 조합을 만들지 않고 연산과정에서 추가되는 문자열이 paraonid 문자열 중 하나이므로 한 번에 추가한다.

어차피 $m$길이의 문자열의 경우 $m - 1$라는 연산을 수행해야 1길이의 문자열이 도출 가능하기 때문에 그 연산 과정에서 연산횟수만큼의 조합이 나온다.

 

#include <iostream>
#include <map>
#include <cmath>
using namespace std;
int main() {
    int t;
    cin >> t;
    while(t--) {
        int n;
        long long ans;
        string s;
        cin >> n >> s;
        ans = n;
        for(int i = 1;i < n;i++) {
            if(s[i] != s[i - 1]) {
                ans += i;
            }
        }
        
        cout << ans << '\n';
    }
    return 0;
}

아 여전히 규칙 속에 숨겨진 패턴 찾는 게 너무 어렵다 ㅠㅡㅠ

하다보면 실력이 늘겠지.......?!