AtCoder Beginner Contest 310 후기 (ABC 310 3솔) /// 앳코더 잠시 중단

업솔빙 제대로 안하고 맨날 3솔따리 4솔따리 해서는 민트에 절대 못 갈 것 같다. E를 안정적으로 풀어낼 수 있을 때까진 수련이 필요할 것 같아 앳코더는 당분간 중단한다.

수련법 : 백준 골3~플5 그래프/다익/uf/TSP/자료구조 문제풀이
(정수론이랑 기하랑 dp도 많이 나오지만 코딩테스트엔 그리 많이 안나오니까 뒷순위로 미룬다)

+ 앳코더 D E 풀이 / D E 합쳐서 30분 잡고 안풀리면 답 보기

 

D가 어려웠다 백트래킹을 떠올리는건 어렵지 않은데 시간복잡도 최적화+ 경우의 수를 줄이기 위한 가지치기가 필요하다

그대로 백준으로 넘어온다면 골드 3이상을 부여하고 싶다

 

E는 개쉬워보이는데 D 버리고 E 풀걸 그랬다....

수험생일 시절에도 그랬고 내가 풀 수 있는 문제인지 아닌지 판단하고 취사선택하는 게 빨라야 총 점수가 잘 나온다

 

D는 결국 못풀었다. 현재 짠 코드에서 TLE가 나는지 확인하기 위해 포기 상태로 제출해 보았는데 TLE나더라

 

A : 영어독해

P를 출력하거나, 메뉴 중 가장 저렴한거 + Q를 출력하기

 

B : 영어독해, 구현

#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(void) {
    fastio;

    int N,M;cin>>N>>M;

    vector<pair<int,set<int>>> vv;

    for (int i = 0; i < N; i++)
    {
        int P,C;cin>>P>>C;
        set<int> ss;
        for (int j = 0; j < C; j++)
        {
            int a;cin>>a;
            ss.insert(a);
        }
        vv.push_back({P,ss});
    }

    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            if(i==j)continue;
            if(vv[i].first<vv[j].first)continue;
            int flg = 0;
            for (int k:vv[i].second)
            {
                if(!vv[j].second.count(k))flg=1;
            }
            if(flg)continue;
            
            if(vv[i].first>vv[j].first||vv[i].second.size()<vv[j].second.size()){
                cout<<"Yes";return 0;
            }
        }
    }
    cout<<"No";
    return 0;
}

문제에서 하라는대로만 하면 되는데, 실수하기 쉬운 문제 같다. 이런문제는 그만풀고싶다

파이썬으로 풀면 훨씬 편하게 풀 수 있었을 것 같다...

 

C : 문자열 reverse, 문자열 비교(set)

set을 이용했다. 입력한 문자열이 중복되는지 / 입력한 문자열을 뒤집은 것이 중복되는지 확인하면서 set에 추가한 뒤

마지막에 set의 사이즈를 출력하면 된다...

 

D : 정교한 백트래킹 또는 매우 정교한 브루트포싱

// Wrong code Wrong code Wrong code Wrong code Wrong code Wrong code Wrong code
#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 N,T,M;
set<int> ss[11];
int teams[11];
int teamscheck[11];
int ans;

void solve(int step){
    if(step==N+1){
        for (int i = 1; i <= T; i++)
        {
            if(teamscheck[i]==0)return;
        }
        ans++;
        return;
    }

    if(teams[step]!=0){
        solve(step+1);
        return;
    }

    for (int j = 1; j <= T; j++)
    {
        int flg=0;
        for (int i:ss[step])
        {
            if(teams[i]==j)flg=1;
        }
        if(flg)continue;

        teams[step]=j;
        teamscheck[j]++;
        solve(step+1);
        teams[step]=0;
        teamscheck[j]--;
    }
}

int main(void) {
    fastio;
    cin>>N>>T>>M;
    for (int i = 0; i < M; i++)
    {
        int a,b;cin>>a>>b;
        if(b<a)ss[a].insert(b);
        if(a<b)ss[b].insert(a);
    }

    teams[1]=1;
    teamscheck[1]=1;

    solve(1);
    cout<<ans;
    return 0;
}
// Wrong code Wrong code Wrong code Wrong code Wrong code Wrong code Wrong code

백트래킹의 기본 틀은 위처럼 짜면 될 것 같은데 정교한 가지치기로 경우의 수 줄이기 + 시간복잡도 줄이기가 더 필요하다

이건 조만간 꼭 다시 풀어봐야겠다...

N<10 T<=N이기 때문에, 비트마스킹을 활용할 수도 있긴 하겠으나 그게 핵심은 아닌 것 같다

뭔가 핵심적인 아이디어가 더 필요함

 

E : 디지털논리회로 / DP또는 누적합같은걸로 뭐 아무튼 간단히 배열에 체크하면 풀릴듯

NAND는 AND의 출력에 NOT을 취한 것이고, 논리회로 지식을 활용하자면 NAND게이트만으로 모든 게이트를 표현할 수 있다

https://doremin.github.io/2020-12-28/21-15

NAND 게이트로 NOT, AND, OR, XOR 게이트 만들기

그렇다고 한다. 기억이 가물가물해서 다른 블로그 글을 첨부한다.

 

1비트끼리 NAND를 계속 해나가는데 이거 규칙성을 찾기 어렵지 않아 보인다

그 규칙성을 찾아서, 배열에 체크하면서 풀면 쉽게 풀릴 것 같다..