SCPC 2021 1차 풀기

매년 여름이면 돌아오는 SCPC

자비롭게도 대학원생도 신청할 수 있게 해주는 덕분에 학사부터 박사까지 한다면 통틀어 대략 10번은 칠 수 있다.

 

아무튼 이번에도 열렸고, 재빨리 신청해서 스벅도 받았다. (사실 이게 목적인 것 같다...)

 

좋은 컨텐츠인 PS 카테고리에 글이 너무 부족하기도 하고,

그렇다고 해서 백준 한 문제마다 글 하나씩 쓰자니 풀기도 벅찬데 쓸 턱이 없으니,

이렇게 뭐라도 하나 있을 때 써 두면 좋겠거니 싶어서 만년초보가 게시글을 하나 채워본다.

 

일단 시간순으로 요약하자면 금요일 15시.

랩실에서 두 문제를 후딱 풀고 저녁먹으러 갔다가 다음날 두 시에 일어나서 3번을 건드리다가 시간이 끝났다...

이번에는 쉬웠다고 하기도 하고 많이 못 풀어서 떨어지나 싶었는데 이상하게 1차를 통과했다.

 

지금 보니까 문제 공개가 아직 안됐다.

기억을 살려서 문제를 적어보면 이렇다.

 

1번.

신입생 오리엔테이션 시간이다. N명의 학생이 일렬로 서 있고 각자 1 이상의 숫자가 i가 적힌 쪽지를 받는다. 학생들은 자신의 오른쪽으로 i 번째 떨어진 사람과 같은 그룹이 된다. 오른쪽으로 i번째에 사람이 없다면 무시한다. 이때 최종적으로 만들어지는 그룹의 숫자는 몇 명인가?

 

나는 별 생각없이 union-find 까지 써가며 왼쪽 부터 시작해서 그룹을 union 시키는 코드로 짰다. 그런데 나중에 알고보니 단방향으로 그룹이 이루어진다는 점에서 문제를 다르게 볼 수 있었다.

 

N명의 학생이 일렬로 서 있고 각자 1 이상의 숫자 i가 적힌 쪽지와 카우보이 올가미를 받는다. 학생들은 자신의 오른쪽으로 i번째 위치에 올가미를 던진다. 

 

그러면 N번째 사람의 오른쪽으로는 올가미 몇 개가 허공을 가르며 튀어나가는데, 이 올가미줄만 잡아 끌면 모든 학생들을 다 끌어 낼 수 있다. 따라서, 이 튀어나온 빈 올가미의 갯수만 세면 전체 그룹이 몇 그룹인지 알 수 있다. 물론 나는 무식하게 그냥 풀었다.

 

코드>>

#include <iostream>
#include <vector>
#include <math.h>
#include <string>
#include <deque>
#include <set>
using namespace std;

int Answer;

int find(vector<int> &g, int n) {
    if(g[n] == n)
        return n;
    return find(g, g[n]);
}

void joint(vector<int> &g, vector<int> &rank, int a, int b) {
    int pa = find(g, a);
    int pb = find(g, b);
    if(pa == pb) return;
    if(rank[pa] < rank[pb]) {
        g[pa] = pb;
    } else {
        g[pb] = pa;
    }
    if(rank[pa] == rank[pb])
        rank[pa]++;
}

int main(int argc, char** argv) {
	int T, test_case;
	// freopen("input.txt", "r", stdin);
	cin >> T;
	for(test_case = 0; test_case  < T; test_case++) {
		Answer = 0;
		int N;
        cin >> N;
        vector<int> dat(N+1,0);
        vector<int> group(N+1,0);
        for(int i = 0; i <= N; i++)
            group[i] = i;
        vector<int> rank(N+1,1);
        for(int i = 1; i <= N; i++) {
            cin >> dat[i];
        }
        for(int i = 1; i <= N; i++) {
            int tar = i + dat[i];
            if(1 <= tar && tar <= N) {
                joint(group, rank, i, tar);
            }
        }
        set<int> all_groups;
        for(int i = 1; i <= N; i++) {
            all_groups.insert(find(group, i));
        }
        Answer = all_groups.size();
		cout << "Case #" << test_case+1 << "\n";
		cout << Answer << "\n";
	}

	return 0;//Your program should return 0 on normal termination.
}

 

 

2번.

이진수 A로부터 이진수 B를 만들 수 있다. 이때 인자로는 k가 들어가며 변환시키는 규칙은 이렇다.
A -- 0101011   k=1  이라면
B -- 1010111   이다.
B_(i) 를 이진수 B 의 i 번째 오는 digit이라고 하면,
B_(i) = A_(i-k) || A(i+k)  이며 범위를 초과하는 A부분은 0으로 취급한다.
A에서는 B를 결정적으로 만들지만, B에서 A를 복구할 때는 여러가지 경우가 가능하다.
이때 B가 주어졌을 때 구할 수 있는 A중에서 가장 작은 값을 구하여라.

경우의 수만 잘 생각해서 짜면 되는 것 같다.

처음에는 단순히 앞에서 부터 A를 채워 나가는 방식을 생각해 봤다. A(i) 번째를 채우기 위해 B(i-k)와 B(i+k) 의 값을 보는 방식. 하지만 당연히 그렇게 단순하게는 문제가 풀리지 않는다.

 

기본적으로 A의 최솟값을 구해야 하기 때문에 A에 최대한 1을 늦게(오른쪽에) 때려넣는 방식으로 진행해야 한다.

그리고 주어진 B값이 1이라면 어떤 A값으로 1이 될 수 있었는지 '해명'해야 한다.

즉 최대한 해명을 늦게 하면 된다.

 

나는 B값이 해명 될 수 있는 경우는 왼쪽의 A가 1인 경우, 또는 오른쪽의 A가 1인 경우 두 가지가 존재하며, 이 경우의 수를 따로 'BtoA' 배열에 저장했다. 

 

1.일단 B_(i)의 가장자리 부분에서는 연결될 A가 하나밖에 존재하지 않기 때문에 k값을 고려해서 BtoA를 1로 줄인다.

2. A를 맨 앞에서부터 채워나가기 시작한다.

 case1.

B(i-k) == 0 ||  B(i+k) == 0 이라면 A(k) 는 0이 될 수 밖에 없다.

 case2.

B(i-k) == 1 이라면 A(k)는 무조건 1이 되며, 존재 이유가 해명되었으므로 B(i-k)는 0으로 바꿔준다. 지금이 A에서 해명할 수 있는 마지막 기회이기 때문에 1이 된다.

 case3.

B(i+k) == 1 && BtoA(i+k) == 1 이라면 edge 값이 1이므로 B(i+k)의 존재 이유를 해명할 수 있는 기회는 지금 뿐이다. 따라서 A(i) = 1 으로 두고 B(i+k) 는 해명되었으므로 0으로 바꾼다. 

 

다 풀고 보니 BtoA 배열이라는 것은 업데이트도 이루어지지 않는 배열인데다가 오른쪽 가장자리에서만 1이 되는 배열이라 단순한 조건문으로 대체할 수 있었다.

 

코드>>

#include <iostream>
#include <vector>
#include <math.h>
#include <string>
#include <deque>
#include <set>
using namespace std;

int main(int argc, char** argv) {
	int T, test_case;
	// freopen("input.txt", "r", stdin);
	cin >> T;
	for(test_case = 0; test_case  < T; test_case++) {
		vector<char> Answer;
		int N, t;
        cin >> N >> t;
        vector<char> bspace(N*3,'-');
        vector<int> bcon(N*3,0);
        vector<char> aspace(N*3,'-');
        vector<char> temp(N*3, '-');
        string inp;
        cin >> inp;

        for(int i = 0; i < N; i++) {
            temp[N+i] = inp[i];
        }

        for(int i = 0; i < N; i++) {
            bspace[N+i] = inp[i];
            if(bspace[N+i] == '1')
                bcon[N+i] = 2;
        }
        for(int i = N; i < N+N; i++) {
            if(bspace[i-t] == '-')
                bcon[i]--;
            if(bspace[i+t] == '-')
                bcon[i]--;
        }
        for(int i = N; i < N+N; i++) {
            if(bspace[i] == '0') {
                aspace[i+t] = '0';
                aspace[i-t] = '0';
            }
        }
        for(int i = N; i < N+N; i++) {
            if(aspace[i] == '0') {
                if(bspace[i+t] == '1')
                    bcon[i+t]--;
                if(bspace[i-t] == '1')
                    bcon[i-t]--;
            }
        }
        for(int i = N; i < N+N; i++) {
            if(aspace[i] == '0') continue;
            if((bspace[i-t] == '0') || (bspace[i+t] == '0')) {
                aspace[i] = '0';
            }
            if((bspace[i-t] == '1') && (bspace[i+t] == '1')) {
                aspace[i] = '1';
                bspace[i-t] = '0';
                bspace[i+t] = '0';
            }
            if( (bcon[i+t] == 1) &&  (bspace[i+t] == '1')) {
                aspace[i] = '1';
                bspace[i+t] = '0';
            }
            if( bspace[i-t] == '1') {
                aspace[i] = '1';
                bspace[i-t] = '0';
            }
        }
        for(int i = N; i < N+N; i++)
            Answer.push_back(aspace[i]);

		cout << "Case #" << test_case+1 << "\n";
        for(auto it : Answer) {
            if(it == '-')
                cout << '0';
            else 
                cout << char(it);
        }
        cout << "\n";       
	}
	return 0;//Your program should return 0 on normal termination.
}

 

3번은 거의 풀지도 못했는데

나중에 문제가 올라오면 다른 적어도 3번까지는 풀어보고 글에 추가해야겠다...