ABC416 4솔

A : 그냥 풀면 된다

B : 설명을 잘 읽고 역시 그냥 풀면 된다. o를 삽입할수 있는가/없는가를 판단하는 플래그를 하나 두고 #이 등장할 때 또는 o를 실제로 삽입할 때 플래그 상태를 바꾼다

 

C : 쌈뽕하게 풀려고 하면 망하고 그냥 다 때려박고 정렬 돌리면 되는 문제

//잘못된 코드

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)
#define ll long long
#define pii pair<int, int>
using namespace std;

// 문자열들을 이어붙인 것 중 X번째 찾기
// 중복순열
int main()
{
    fastio;
    ll N, K, X;
    cin >> N >> K >> X;
    X--;
    vector<string> v(N);
    for (ll i = 0; i < N; i++)
        cin >> v[i];
    sort(v.begin(), v.end());
    vector<ll> dds = {1};
    for (ll i = 0; i < K - 1; i++)
        dds.push_back(dds[i] * N);
    reverse(dds.begin(), dds.end());
    
    for (ll i = 0; i < dds.size(); i++)
    {
        ll z = X / dds[i];
        X %= dds[i];
        cout << v[z];
    }
    return 0;
}

중복순열이므로, 나누기/나머지 연산을 이용해 특정 순서의 원소가 고정된 중복순열이 몇개 존재하는지 예측해서

전처리 O(N), 출력 O(K)으로 풀려고 했는데............

 

주어지는 string원소들의 길이가 다르기 때문에 이어붙인 string이 항상 사전순임을 보장할 수 없다. 그렇기 때문에 결국 다 때려박고 정렬을 돌려야 한다(완전탐색)

위를 생각하지 못해서 C번 문제에서 말렸고 이번 ABC도 망함

 

D : MAX heap와 MIN heap 한개씩을 이용해, 나머지연산을 최대한 많이 사용하는 문제

이문제는 문제 설명을 제대로 안 읽어서 말렸다.

이걸 출력해야 하는데

전체 결과에도 MOD M을 해서 출력하다가 논리적으로 맞는데 이거 왜 안되지를 한참 생각했다

아무튼 이 문제를 풀기 위해선 나머지연산을 취하는 횟수를 최대한으로 만들면 되는데(그리디) 이걸 계산하기 위해 A는 최대힙에 넣어놓고 B는 최소힙에 넣어놓는다.

최대힙의 꼭대기 원소와 최소힙의 꼭대기 원소가 M보다 크면 나머지연산을 적용하고 pop한다

그렇지 않다면 최소힙의 꼭대기 원소는 어떻게 해도 나머지 연산을 적용할 수 없는 녀석이기 때문에 따로 빼놓는다

 

마지막에, 따로 빼놓은 녀석들과 최대힙에 남아있는 녀석들을 다 ans에 더해 주면 답 나옴

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)
#define ll long long
#define pii pair<int, int>
using namespace std;

int main()
{
    fastio;
    ll T;cin>>T;
    while (T--)
    {
        ll N,M;cin>>N>>M;
        ll ans = 0;
        priority_queue<ll,vector<ll>,less<ll>> MAH,REM;
        priority_queue<ll,vector<ll>,greater<ll>> MIH;
        for (int i = 0; i < N; i++)
        {
            ll a;cin>>a;MAH.push(a%M);
        }
        for (int i = 0; i < N; i++)
        {
            ll a;cin>>a;MIH.push(a%M);
        }
        while (!MIH.empty())
        {
            if(MIH.top()+MAH.top()<M){
                REM.push(MIH.top());
                MIH.pop();
            }
            else{
                ans+=(MIH.top()+MAH.top())%M;
                // cout<<MIH.top()<<" "<<MAH.top()<<":"<<ans<<"<<\n";
                MIH.pop();MAH.pop();
            }
        }
        // cout<<"\n---\n";
        while (!MAH.empty())
        {
            ans+=(MAH.top()+REM.top())%M;
            // cout<<REM.top()<<" "<<MAH.top()<<":"<<ans<<"<<\n";
            MAH.pop();REM.pop();
        }
        cout<<ans<<"\n";
    }
    return 0;
}

 

E : 플로이드를 이용하는데, 쿼리에 N제곱, 업데이트에 N제곱 + 공항을 별도의 노드로 처리하는 아이디어가 필요한 문제

처음보는 아이디어인데 문제는 정말 좋은듯??

플로이드를 쓴다는건 시간복잡도까지 다 따져서 판단 성공했는데 공항을 잘 관리하는게 관건이다

꼭 다시 풀어보고 백준에서 비슷한 문제를 풀어보자

 

이번 앳코더 총평

C번 문제와 D번 문제에서 말렸지만 문제 자체는 정말 좋은 것 같다 E번 문제도 재밌음

정확하게 빨리 푸는 능력이 많이 약해진 것 같다 특히 C번문제는 정확한 판단이 없다면 바로 낚시에 걸리는 문제고 내가 딱 걸렸음

그래서 최근 앳코더 다 망하고 똥색됐다

AI가 너무 좋아져서 그런지 최근 나오는 문제들이 전체적으로 어렵고 풀더라도 점수를 잘 안주는거 같기도 함

요즘은 게임도 잘 안하는데 심심하면 앳코더 기출문제를 더 풀어봐야겠다

백준 단계별로풀어보기도 더 밀고