BOJ 29198 - 이번에는 C번이 문자열

BOJ 29198 - 이번에는 C번이 문자열

“문자열 그리디 문제”

BOJ 29198 - 이번에는 C번이 문자열

문제 링크



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

ll N, M, K;
vector<string>vp;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    cin >> N >> M >> K;
    for (int i = 0; i < N; i++){
        string s; cin>>s; sort(s.begin(), s.end());
        vp.push_back(s);
    }
    sort(vp.begin(), vp.end());
    string t;
    for (int i = 0; i < K; i++) t += vp[i];
    sort(t.begin(), t.end());
    cout << t;
    return 0;
}
  • 문자열 그리디 문제이다. 로직은 간단한데 아주 조그마한 반례를 찾아내지 못해서 결국 chatgpt에게 반례를 받아버리고 말았다. 또 또 또 자괴감 stack += 1해버리고 말았다…


for (int i = 0; i < N; i++){
    string s; cin>>s; 
    sort(s.begin(), s.end()); // 중요!
    vp.push_back(s);
}
  • 받을 때부터 쏘트를 해주지 않으면, 위에 찌피티가 쪄준 예외에서 실패하게 된다. 왜 이런 생각을 못했을까…