AtCoder Beginner Contest 307 후기 (ABC 307 3솔)

 

C 개 드럽다
구현량 많고 실수하기 쉬운 순수 구현 문제이다

C를 못풀었는데도 레이팅 1021이 나와서 순방에 성공했다

 

C에 대부분의 시간을 사용했고 E는 쳐다볼 시간도 없었다

 

A - 걍풀면됨

 

B - 펠린드롬, 브루트포스, 문자열

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

bool ispel(string s){
    int ssize = s.length();

    int l = 0,r = ssize-1;
    
    while (l<r)
    {
        if(s[l]==s[r]){
            l++;r--;
        }
        else{
            return 0;
        }
    }
    return 1;
}

int main(){
	fastio;
    
    int N;cin>>N;
    vector<string> v;
    for (int i = 0; i < N; i++)
    {
        string S;cin>>S;
        // a번째랑 b번째 합쳐서 펠린드롬되면 yes
        v.push_back(S);
    }

    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            if(i==j)continue;
            string c = v[i]+v[j];
            if(ispel(c)){
                cout<<"Yes";return 0;
            }
        }
    }
    cout<<"No";
    
	return 0;
}

i와 j는 distinct한 숫자라고 문제 설명에 나와 있고, j가 i보다 클 수 있음을 예제를 보고 알 수 있다. 그 부분에서 실수하지만 않으면 어렵지 않은 문제

 

C - 구현, 브루트포스

이 문제는 다시 풀 생각이 없다.... 왜 이렇게 냈는지 모르겠다

 

요약하자면, 두개의 시트 A와 B를 적절히 겹치고 마지막에 필요없는 부분을 잘라내어 시트 X를 만드는 문제이다

시트는 검은색 부분과 투명한 부분으로 이루어진 H*W크기의 직사각형이고, 시트 A와 B를 적절히 겹치더라도 A와 B의 모든 검은색 부분이 만들어진 시트에 포함되어야 한다

 

-> 시간제한이 2초이고 시트의 크기가 최대 10*10으로 주어지기 때문에 브루트포스로 풀어도 문제가 없으나,

가장 단순하게 생각할 경우, 4중 for문을 이용해 A와 B의 왼쪽 위 꼭짓점의 오프셋을 정하고

그렇게 겹쳐 만들어진 시트를 임시로 저장하고

 

만들어진 시트와 X를 비교하면서 모두 일치하는지 확인하면 됨.

 

근데 이 문제를 실수하기 쉬운 이유는

1. 시트 A와 B의 오프셋을 옮기며 겹치다 보면 시트 X의 범위를 넘어가고 여기서 segfault가 발생하기 쉬움

2. 문제 조건이 다소 생소함. A와 B의 모든 검은색 부분이 포함되어야 한다는 거랑, 마지막에 잘라내도 된다는 거

3. 문제 설명도 길고 구현할 게 많음

이러하다

 

D - 스택, 문자열

아주 쉽게 나왔다 얘가 C로가도 될 것 같다

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

int main(){
	fastio;
    int N;string S;cin>>N>>S;

    stack<char> ss;

    for (int i = 0; i < N; i++)
    {
        if(ss.empty()){
            ss.push(S[i]);
            continue;
        }
        else{
            if(S[i]==')'){
                //좌괄호가 나오거나 스택이 빌때까지 뽑아내기
                //이후 출력
                string tmp = "";
                while (!ss.empty()&&ss.top()!='(')
                {
                    tmp=ss.top()+tmp;
                    ss.pop();
                }
                if(ss.empty()){//스택이 비었음
                    cout<<tmp<<")";
                }
                else{//괄호가 이루어졌음
                    ss.pop();
                }
            }
            else{
                ss.push(S[i]);
            }
        }
    }
    string ans = "";
    while (!ss.empty())
    {
        ans = ss.top()+ans;
        ss.pop();
    }
    cout<<ans;
	return 0;
}

비슷한 문제가 많으므로 스택이라는 아이디어를 생각하기도 어렵지 않고, 직접 테스트케이스를 작성해 테스트하기도 쉽다

 

E - 대충 읽어봐도 조합론

1~N의 번호가 할당된 N명의 사람들에게 0~M-1의 숫자카드 중 하나를 할당하는 방법은 M^N가지가 존재한다.

근데 이 문제에서는 사람들이 원형으로 손에 손잡고 서 있으면서,

모든 인접한 사람들끼리는 다른 번호의 숫자카드를 받아야 한다고 함. -> 조합론

 

그리고 왠지 DP로 풀릴 것 같다. 아님말고