[PS] 동전 쌍 뒤집기 / C++ (백준 32034번)

 

UCPC 2024 예선 J번 문제로, 대회 도중에 팀원이 풀던 문제를 이어받아 반례를 찾았고, 이를 해결한 뒤 제출했지만 끝내 풀지 못하고 아쉬워하며 대회를 마쳤다.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int n;
int ans = 0;
string coins;
vector <int> tPos;

int f(int left, int right) {
    for (int i = left + 1; i < right; i++) {
        for (int j = i + 1; j < right; j++) {
            if ((tPos[j] - tPos[i]) % 2 == 1 && (j - i) % 2 == 1) { // 사이의 동전 개수가 짝수, T 개수가 짝수
                if (j != i + 1) {
                    int c = f(i, j);
                    if (c == -1) {
                        continue;
                    }

                }
                ans += (tPos[j] - tPos[i]);
                i = j;
                break;
            }
            if (j == right - 1) {
                return -1;
            }

        }
    }
    return 0;
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int t;
    cin >> t;

    while (t--) {
        tPos.clear();
        cin >> n;
        cin >> coins;
        ans = 0;
        int leng = coins.length();
        for (int i = 0; i < leng; i++) {
            if (coins[i] == 'T') {
                tPos.push_back(i);
            }
        }

        int size = tPos.size();
        if (size % 2 != 0) { // 홀수개면 불가
            cout << "-1\n";
        }
        else if (size == 0) { //0개일 때
            cout << "0\n";
        }
        else { //t가 2개 이상인 짝수개일 때
            bool flag = false;
            for (int i = 0; i < size; i++) {
                for (int j = i + 1; j < size; j++) {
                    if ((tPos[j] - tPos[i]) % 2 == 1 && (j - i) % 2 == 1) { // 사이의 H개수가 짝수
                        if (j != i + 1) {
                            int c = f(i, j);
                            if (c == -1)continue;
                        }
                        ans += (tPos[j] - tPos[i]);
                        i = j;
                        break;
                    }
                    if (j == size - 1) {
                        flag = 1;
                        break;
                    }
                }
                if (flag)break;
            }

            if (flag) cout << "-1\n";
            else cout << ans << "\n";
        }
    }
    return 0;
}

애드혹 로직을 떠올려서 짠 코드이다.

'(tPos[j] - tPos[i]) % 2 == 1': 사이의 T개수가 짝수인지,

'(j - i) % 2 == 1': 사이의 H개수가 짝수인 지 판별하여 처리하는 로직이다.

반례는 결국 찾지 못했지만 아마 값이 매우 커지면 한 틱 차이로 틀릴 것 같았다.

 

해결 방법

 이후 로직은 유지하고 틀을 스택으로 고쳐 해결했다.

#include <iostream>
#include <stack>
#include <algorithm>
#include <vector>
using namespace std;


string coins;
vector <int> tPos;

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n;
    long long int ans = 0;
    int t;
    cin >> t;

    while (t--) {
        tPos.clear();
        cin >> n;
        cin >> coins;
        ans = 0;
        int leng = coins.length();
        for (int i = 0; i < leng; i++) {
            if (coins[i] == 'T') {
                tPos.push_back(i);
            }
        }

        int size = tPos.size();
        if (size % 2 != 0) { // 홀수개면 불가
            cout << "-1\n";
        }
        else if (size == 0) { //0개일 때
            cout << "0\n";
        }
        else {//t가 2개 이상인 짝수개일 때
            stack<int> st;
            for (int i = 0; i < size; i++) {
                if (st.empty()) {
                    st.push(i);
                    continue;
                }
                int j = st.top();
                if ((tPos[i] - tPos[j]) % 2 == 1) { // 사이의 동전 개수가 짝수
                    ans += (tPos[i] - tPos[j]);
                    st.pop();
                }
                else {
                    st.push(i);
                }
            }

            if (st.size()) cout << "-1\n";
            else cout << ans << "\n";
        }
    }
    return 0;
}