cdjs의 코딩 공부방

오늘은 G5~G1 랜덤 디펜스를 해봤다.

원래 순서대로 푸려고 했는데, G4랑 G2 라인 문제가 잘 안떠올라서 G5-G3-G4-G1-G2 순으로 풀렸다.

총 풀이 시간: 약 2시간 20분

G5 | 12887 - 경로 게임

시도 횟수: 1회

체감 난이도: G5

풀이 쓸 의향: 下

풀이

여담: 여기까지는 10분컷이었는데,,, :(

G3 | 19535 - ㄷㄷㄷㅈ

시도 횟수: 2회

체감 난이도: G3~G2 사이 어딘가

풀이 쓸 의향: 中

풀이

여담: DFS / BFS 문제인줄 알았는데 무조건 시간초과 난다는 것을 깨닫고 후다닥 풀이를 틀어버린 문제. 상당히 흥미로운 문제였다.

G4 | 25307 - 시루의 백화점 구경

시도 횟수: 3회

체감 난이도: G3

풀이 쓸 의향: 下

풀이

여담: 최적화를 제대로 안해서 한 번, 그냥 급하게 내다가 한 번 더 틀렸다. 원래 이렇게 오래 걸릴 문제는 아니었는데 마네킹에서 BFS를 돌릴 때 최적화하는 방법이 뭔가 머리에서 안떠올랐다. 피곤한 날엔 코딩하지 말아야지...

G1 | 21320 - 순간이동 여행

시도 횟수: 1회

체감 난이도: G1

풀이 쓸 의향: 中

풀이

여담: 풀이가 꽤 재밌고 dp 점화식 구하는 과정이 흥미로웠다.

G2 | 1797 - 균형잡힌 줄서기

시도 횟수: 2회

체감 난이도: G2

풀이 쓸 의향: 下

풀이

여담: 처음에 prefix sum이라고 잘 생각했다가 갑자기 턱 막혀서 위의 G1 문제로 넘어갔었다.

DP로 해결되지 않을까 하는 마음에 DP 점화식을 세워보려던게 패착이었던 것 같은데, 사실 이 문제에서 prefix sum을 안쓰면 딱히 할 수 있는게 없어 보였음에도 부분합 풀이를 치워두고 DP 풀이로는 왜 갔던걸까....

P4 | 17408 - 수열과 쿼리 24

풀이 시간: 약 25분

시도 횟수: 4회

체감 난이도: P4 날먹

풀이 쓸 의향: 下

풀이

여담: 이날 코포치느라 글도 못쓰고 문제도 별로 못풀었는데, 코포도 조져서 슬프다,,, :(

G3 | 11562 - 백양로 브레이크

풀이 시간: 약 25분

시도 횟수: 2회

체감 난이도: G3

풀이 쓸 의향: 下

풀이

여담: 그냥 문득 G3이 어느 정도 난이도였나 기억하려고 한번 풀어봄.

P5 | 20158 - 사장님 달려가고 있습니다

풀이 시간: 약 1시간 + 20분

시도 횟수: 무려!!! 14회

체감 난이도: 마음같아선 P4주고싶지만 내실수로 이렇게된거라 P5 하위권...

풀이 쓸 의향: 下

풀이

여담: 이틀 전에 풀다가 때려치고 다시 풀었다. 참 많은 곳에서 실수를 해버려서... ;(

달려가는 중간에 있는 구역도 장애물이 있으면 밟으면 안된다는 점에 주의할 것....

P4 | 10220 - Self Representing Seq

풀이 시간: 약 25분 + 10분

시도 횟수: 2회

체감 난이도: X

풀이 쓸 의향: 下

풀이

여담: 사실 N=1부터 N=16쯤까지 브루트 포스로 한번 다 해보니까 이상한 규칙이 보이길래 일단 때려박아보고 AC 맞은 뒤에 증명함...

태그에 "런타임 전의 전처리" 박으려다가 꾹 참고 그냥 뒀는데, 증명 후 풀이였으면 정말 P3 위로 올라가는 정신나간 난이도의 문제였을 것으로 추정됨.

사실 더 풀려고 했는데 문제 하나 잘못 읽고 삽질하는 바람에 나중에 푸는 걸로.... ;(

P4 | 1412 - 일방통행

풀이 시간: 약 40분

시도 횟수: 2회

체감 난이도: P4 최하위권

풀이 쓸 의향: 中

풀이

여담: 이 아이디어가 굉장히 빨리 떠올라서 운 좋게 빠르게 풀 수 있었다. 만약 이 아이디어 상상이 안됐다면, 혹은 관찰 첫발을 잘못 밟았으면 충분히 높은 난이도라고 생각될 수 있겠다 싶다.

https://www.acmicpc.net/problem/10542

1. 문제

- $N$명의 사람들이 마피아 게임을 진행한다.

- 각 사람들이 마피아일것 같은 사람을 투표하게 되는데, 시민은 자신을 제외한 다른 사람 아무나 투표하고, 마피아는 시민 중 한 명에게 투표한다.

- 마피아일 수 있는 사람 수의 최대값을 출력하라.

2. 힌트

힌트 1

힌트 2

힌트 3

3. 문제 관찰 과정 및 풀이

3-1. 문제 관찰 과정

문제를 처음 봤을 때, 솔직히 조금 어지러웠다. 문제 지문이 살짝 이해하기 힘든 점도 있기는 했지만, 그보다도 대체 문제 풀이를 어떻게 시작해야 할지 감도 안잡혔기 때문이다.

조금 생각하다 보니, 참가자의 투표를 유향 그래프로 나타내어 그래프를 직접 그려보면 문제 상황 자체를 쉽게 이해할 수 있다 생각이 들어 그림판을 켜서 예제 입력을 직접 그리며 관찰해 보았다.

"마피아는 서로 마피아를 투표하지 않는다" 라는 것은, 그래프가 a->b로 연결되어 있을 때 a번 사람이 마피아라면 b번 사람은 마피아일 수 없다는 것을 의미한다.

그런데, 어차피 a->b로 연결되어 a번 사람과 b번 사람이 동시에 마피아가 될 수 없다면 그래프를 유향 그래프로 그리는 것이 오히려 불편해지기 때문에, 무향 그래프로 바꾸어 생각해 보았다.

이렇게 무향 그래프로 바꾸고 나면 "서로 이웃하지 않는 노드들을 최대한 많이 선택할 때, 그 노드들의 개수를 구하여라" 라고 문제를 변환하여 생각할 수 있다.

처음에는 DP 문제일까 하고 고민해 보았는데, 어떻게 구현해도 시간 안에 예쁘게 구현될 것 같지 않아서 때려쳤다.

그렇게 계속 관찰하다가, "일단 반드시 골랐을 때 이득인 노드가 있을까?" 라는 생각으로 그래프를 살펴보았다.

가장 처음에는 연결된 개수가 가장 작은 것을 먼저 고르면 되는 그리디 문제인가 고민해 보았지만, 바로 반례를 찾아 폐기되었다.

그런데 반례를 만들다가 a->b->c로 일직선으로 (즉, 옆으로 새는 길 없이) 연결된 형태이며 a, b번 노드가 둘 다 단말 노드라면 b보다는 a를 고르는 것이 최적이라는 사실을 발견했다.

이를 조금 더 확장하여 문제를 해결해 보자.

3-2. 문제 풀이

각 정점을 사람의 번호, 간선은 서로가 투표했는지 여부에 따라 무향 그래프를 하나 생성한다.

그렇다면 문제가 "서로 이웃하지 않는 노드들을 최대한 많이 선택할 때, 그 노드들의 개수를 구하여라" 로 치환된다.

이 때, 반드시 단말 노드를 가장 먼저 고르는 것이 최적이라는 사실을 관찰을 통해 짐작할 수 있다.

이유는 간단한데, 단말 노드의 경우 간선이 단 하나만 연결되어 있으므로 해당 노드를 골랐을 때 고르지 못하게 되는 노드는 단 하나만 생긴다.

그런데 단말 노드 대신 고르지 못하게 되는 다른 노드를 고르게 되면 반드시 단말 노드를 고른 것보다 고를 수 있는 노드 수가 항상 같거나 적으므로, 단말 노드를 고르는 것이 더 최적해라는 것을 알 수 있다.

또한, 단말 노드가 존재하지 않을 때까지 노드를 고르면 나머지 그래프들은 전부 거대한 사이클 하나로 이루어진 그래프가 되는데, 사이클 하나로 이루어진 그래프에서는 반드시 (노드 개수 / 2) 만큼의 노드를 고를 수 있으니 각 사이클을 DFS로 돌며 크기를 확인하고 값을 더해주면 된다.

주의할 점은, 이 문제의 경우 그래프 하나가 아니라 끊어져 있는 서로 다른 여러 그래프가 나올 수 있으므로 사이클 크기 처리를 해 줄때 각 그래프에 대해 한 번씩 전부 돌며 연산해주어야 한다.

4. 코드

너무 신난 상태로 코드를 짜서 그런지 코드가 많이 더럽다.

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

vector<int> visited;
vector<vector<int>> v;

int dfs(int node, int x) {
    visited[node] = 1;
    for (int i=0; i<v[node].size(); i++) {
        if (visited[v[node][i]])    continue;
        return dfs(v[node][i], x+1);
    }
    return x;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);  cout.tie(NULL);
    int n;
    int a[500005];
    int cnt[500005];
    int ans = 0;
    memset(cnt, 0, sizeof(cnt));
    cin >> n;
    
    v = vector<vector<int>>(n+1);
    visited = vector<int>(n+1, 0);
    
    for (int i=1; i<=n; i++) {
        cin >> a[i];
        if (a[i] < i && a[a[i]] == i) {	// 서로가 서로를 지목한 경우;
            continue;
        }
        v[i].push_back(a[i]);
        v[a[i]].push_back(i);
        cnt[a[i]]++;	// 연결된 간선 개수
        cnt[i]++;
    }
    
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    for (int i=1; i<=n; i++) {
        pq.push({cnt[i], i});
    }
    
    while (!pq.empty()) {
        int sz = pq.top().first;
        int node = pq.top().second;
        pq.pop();
        if (visited[node])  continue;
        if (sz>1)  break;
        
        ans++;
        visited[node] = 1;
        for (int i=0; i<v[node].size(); i++) {
            int nnode = v[node][i];
            if (visited[nnode]) continue;
            visited[nnode] = 1;
            for (int j=0; j<v[nnode].size(); j++) {
                if (visited[v[nnode][j]])   continue;
                cnt[v[nnode][j]]--;
                pq.push({cnt[v[nnode][j]], v[nnode][j]});
            }
        }
    }
    
    for (int i=0; i<n; i++) {
        if (visited[i]) continue;
        ans += dfs(i, 1) / 2;
    }
    
    cout << ans;
}

5. 여담

오랜만에 정말 마음에 드는 문제를 풀었다. 관찰 과정부터 풀이 구현까지 전부 즐겁게 해결한 문제.

태그 중에 분리 집합이 있는 것을 보아하니 분리 집합으로도 풀 수 있는 모양이다.

P3 | 6132 - 전화선

풀이 시간: 1시간

시도 횟수: 2회

체감 난이도: P3

풀이 쓸 의향: 上

풀이

여담: 다른 사람들은 죄다 DP로 푼 것 같은데 나 혼자만 그리디로 푼 것 같다. 문제 관찰 과정과 그 관찰을 토대로 그리디 알고리즘을 구현하는 과정이 즐거웠다.

P5 | 1131 - 숫자

풀이 시간: 1시간 10분

시도 횟수: 2회

체감 난이도: P5

풀이 쓸 의향: 下

풀이

여담: 문제 보자마자 아이디어 거의 10분만에 떠올려놓고 구현에서 죽쑨거 못찾고 1시간 삽질함; 죽고싶다...

P3 | 12016 - 라운드 로빈 스케줄러

풀이 시간: 약 50분

시도 횟수: 2회

체감 난이도: P3 하위권

풀이 쓸 의향: 下

풀이

여담: 4년 전에는 뭣도 모르고 시간 초과를 냈던 문제인데, 이제야 스스로 해결할 수 있게 되었다. 만세!

딱히 재미있는 관찰이 필요한 게 아니라 세그트리를 잘 활용하기만 하면 풀리는 문제여서 딱히 재미는 없었다.

P5 | 15808 - 주말 여행

풀이 시간: 30분

시도 횟수: 무려 7회

체감 난이도: P5 하위권

풀이 쓸 의향: 下

풀이

여담: 정답이 0보다 작을 수 있음을 고려하지 않고 풀다가 혼쭐났음. 아니 영선아 여행 기대치가 음수면 대체 왜 여행을 가는거니??

P4 | 14927 - 전구 끄기

풀이 시간: X

시도 횟수: 1회

체감 난이도: X

풀이 쓸 의향: 下

풀이

여담: https://www.acmicpc.net/problem/14939 이전에 풀었던 문제와 너무 동일해서 그냥 풀이 박아버렸음... 솔직히 골드 난이도는 진짜 말도 안된다고 생각하고, 사람마다 개인차가 있겠지만 P5 ~ P4 사이인듯.

P5 | 9463 - 순열 그래프

걸린 시간: 20분

체감 난이도: 어쩔수 없이 P5 주는 정도

시도 횟수: 1회

풀이 쓸 의향: 下

풀이:

여담: 그냥 세그트리 쓰면 풀리는 세그트리용 날먹 문제. seg 구현할때 등호 넣으면 안되는 식에 등호넣어서 5분 날림.

P4 | 1124 - 바닥 장식

걸린 시간: 1시간 30분

체감 난이도: P4 상위권

시도 횟수: 6회

풀이 쓸 의향: 下

풀이:

여담: 내가이겼어내가이겼어내가이겼어내가이겼어내가이겼어내가이겼어내가이겼어내가이겼어내가이겼어내가이겼어내가이겼어내가이겼어내가이겼어내가이겼어내가이겼어내가이겼어내가이겼어내가이겼어내가이겼어내가이겼어내가이겼어내가이겼어내가이겼어내가이겼어내가이겼어내가이겼어내가이겼어내가이겼어내가이겼어내가이겼어내가이겼어

문제 보자마자 풀기싫어서 몸비틀다가 풀이 시작하자마자 문제 잘못읽고 풀다가 때려치려고 하다가 다시 풀다가 틀려서 예외처리하다가 정신이 나가버릴뻔함

저번에 풀었던 리그 (https://www.acmicpc.net/problem/3031)보다 예외 처리랑 구현 더 빡센 문제는 이게 처음인듯

풀이 메모

P3 | 21725 - 더치페이

걸린 시간: 1시간 15분

체감 난이도: P3 중/하위권

시도 횟수: 9회

풀이 쓸 의향: 中

풀이:

여담: 돈 0원 송금하면 안된다는 조건 때문에 한번 틀렸고, 다른 별 이상한 실수해서 틀렸던건데 풀이 증명 다시하고 반례 이것저것 넣고 assert 조지고 하느라 시도 횟수가 늘어났다.

아니 문제 알고리즘 바로 떠올리고 잘 풀어놓고 왜 구현에서 이상한 실수 하는지 모르겠는데 그냥 지금 졸려서 그렇다고 생각하자...

풀이 메모