cdjs의 코딩 공부방

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 조지고 하느라 시도 횟수가 늘어났다.

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

풀이 메모

G5 | 14699 - 관악산 등반

걸린 시간: 약 15분 (부정확)

체감 난이도: G5 ~ G4 사이 그 어딘가 애매한 지점

시도 횟수: 1회

풀이 쓸 의향: 下

풀이:

여담: 친구가 암만봐도 골드 5 아닌것같다고 해서 풀어본 문제.

솔직히 아이디어 자체는 G5가 맞는데 그래프기도 하고 이런저런 구현방법 잘 모르면 시간 끌릴수도 있겠다 싶어서 G4로 난이도 기여함.

P5 | 2463 - 비용

걸린 시간: 45분

체감 난이도: P4 하위권

시도 횟수: 2회

풀이 쓸 의향: 中

풀이:

여담: disjoint set 구현할 때 두 root값(그래프 크기값)을 곱하는 부분이 있었는데, root값을 int로 둬서 한번 틀림.

솔직히 처음 봤을때 바로 MST(Maximum)이 떠올랐는데, 실상 풀이는 MST를 안쓰는게 더 편해서 오히려 생각이 더 꼬였던 것 같다.

(풀이 메모)

P4 | 1280 - 나무 심기

걸린 시간: 약 40분 (부정확)

체감 난이도: P5 상위권

시도 횟수: 3회

풀이 쓸 의향: 下

풀이

여담: 

나머지 연산 실수때문에 한 번, 값 범위가 0부터 시작인거 못봐서 한 번 틀렸다.

P5 | 14572 - 스터디 그룹

걸린 시간: 약 30분

체감 난이도: P5 하위권

시도 횟수: 1회

풀이 쓸 의향: 下

풀이

여담: vector<pair<int, vector<int>>>라는 괴상한 자료구조를 만들어서 풀었다.

실력 차이가 D 이하인 모든 구간에서 최대한 많은 사람을 넣도록 투포인터로 풀린다는 아이디어가 쉬운 사람한테는 너무 쉽고, 어려운 사람한테는 너무 어렵게 보일만 한듯.

P3 | 10542 - 마피아 게임

걸린 시간: 1시간 10분

체감 난이도: P3

시도 횟수: 8회

풀이 쓸 의향: 上

풀이

여담: 정말 재밌게 푼 문제.

중간에 많이 해메서 좀 코드가 많이 더럽다. 남은 cycle 처리를 이상하게 해서 자꾸 틀리다 결국 발견해서 풀었다.

(풀이 메모)