[C++] 악마 게임 (백준 16677번)

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

 

#include <iostream>
using namespace std;

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

    string s;
    int n;
    cin >> s >> n;
    int sn = s.size();

    double ans = 0;
    string anss = "No Jam";

    while (n--) {
        string a;
        double g;
        cin >> a >> g;
        int an = a.size();

        int cnt = 0;
        int idx1 = 0;
        int idx2 = 0;

        bool psb = true;
        while (idx2 < an) {
            if (idx1 < sn && s[idx1] == a[idx2]) {
                idx1++;
                idx2++;
            } else {
                idx2++;
                cnt++;
            }
        }

        if (idx1 == sn) {
            double tmp = g / cnt;
            if (tmp > ans) {
                ans = tmp;
                anss = a;
            }
        }
    }

    cout << anss << '\n';
}

단순 구현 문제이긴 한데 생각보다 오래 헤매서 공익을 위해 또는 그냥 기록용으로 글을 남긴다...

 

원래 단어 s, 원래 단어의 길이 sn

글자를 끼워 넣어 만들어야 하는 단어 a, 만들어야 하는 단어의 길이 an

만들어야 하는 단어를 끝까지 읽으면서, 글자가 같으면 인덱스를 같이 증가시키고 다르면 만들어야 하는 단어의 인덱스만 증가시킨다. 이 때, 후자의 경우 글자를 끼워야 하므로 cnt를 1만큼 증가시킨다.

만들어야 하는 단어를 전부 읽었음에도 원래 단어가 남아있다면, 그건 만들어야 하는 단어가 되기 위해서는 글자를 제거해야 한다는 것을 의미한다. 즉, 글자 추가만으로는 만들 수 없으므로 "No Jam"이 되는 것이다. 

 

정리해서 적으니까 쉬운 것 같은데 이걸 왜 이렇게 오래 고민한걸까 (AC)