[Codeforces] #2244A - Iskander and Drawings [C++]

문제 링크

---

1. 아이디어

#과 *로 이루어진 문자열이 주어지고 *은 빈 공간, #는 선을 의미한다. 각 문자열에 대해 선을 지우는 데 가장 오래 걸리는 시간을 구하는 문제로 각 선은 좌우에서 매초 1센티미터씩 지울 수 있다. 따라서 주어진 문자열에서 연속된 #으로 이루어진 가장 긴 선을 찾아 길이를 구한 후 이를 2로 올림 나눗셈을 한 값이 해당 문자열에서 가장 긴 선을 지우는 데 걸리는 시간이 된다.

---

2. 복잡도

접근	시간	공간
풀이	$O(T \times N)$	$O(N)$

($T$ = 테스트 케이스 수, $N$ = 케이스당 s의 길이의 최댓값)

---

3. 코드

풀이 [C++]

#include <bits/stdc++.h>
using namespace std;

void solve() {
    int n;
    string s;
    cin >> n >> s;

    int mx = 0, cnt = 0;
    for (char c : s) {
        if (c == '#') {
            cnt++;
        } else {
            cnt = 0;
        }

        mx = max(mx, (cnt + 1) / 2);
    }

    cout << mx << '\n';
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int t;
    cin >> t;
    while (t--) solve();
}

---