Gumgood  
CP Algorithm

프로그래머스 월간 코드 챌린지 시즌2 4월

By Sangwon Lee Posted Apr 28, 2021

참가후기

전체 8등을 했다. 지문이 간단하고 명확했고 무려 한국어였다(…). 항상 영어 지문을 잘못 해석해서 고생했던 나한테 유리했다. 국내에도 이렇게 좋은 대회가 생기다니 앞으로도 자주 참가해야겠다.

A. 음양 더하기

몇 개의 정수들이 있다. 이 정수의 절대값을 나타내는 수열과 부호를 나타내는 boolean 배열이 주어진다. 이 때, 모든 정수의 합을 구하는 문제다.

signs[]를 보고 부호를 정해서 더하면 된다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

#include <string>
#include <vector>

using namespace std;

int solution(vector<int> absolutes, vector<bool> signs) {
    int answer = 0;

    int n = (int)absolutes.size();
    for(int i=0;i<n;++i){
        if(signs[i]) answer += absolutes[i];
        else answer -= absolutes[i];
    }

    return answer;
}

B. 괄호 회전하기

(), [], {}로 이뤄진 괄호 문자열이 주어진다. 이를 왼쪽으로 $x$번 shift를 했을 때 올바른 괄호 문자열이 되는 $x$의 개수를 구하는 문제다.

괄호 문자열의 길이 $N$은 최대 $1000$으로 여유롭다. 모든 $x$에 대해 shift해서 올바른 괄호 문자열인지 판단하는데 $O(N)$이고 $N$개의 $x$에 대해 이를 반복하면 전체 $O(N^2)$에 해결할 수 있다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

#include <string>
#include <vector>
#include <deque>
#include <stack>

using namespace std;

bool chk(deque<char> &dq){
    stack<char> s;
    for(int i=0;i<(int)dq.size();++i){
        if(dq[i]=='(') s.push(dq[i]);
        if(dq[i]=='[') s.push(dq[i]);
        if(dq[i]=='{') s.push(dq[i]);
        if(dq[i]==')'){
            if(s.empty() || s.top() != '(') return false;
            else s.pop();
        }
        if(dq[i]=='}'){
            if(s.empty() || s.top() != '{') return false;
            else s.pop();
        }
        if(dq[i]==']'){
            if(s.empty() || s.top() != '[') return false;
            else s.pop();
        }
    }
    return s.empty();
}

int solution(string s) {
    int answer = 0;

    int n = s.size();
    deque<char> dq;
    for(int i=0;i<n;++i)
        dq.emplace_back(s[i]);
    for(int i=0;i<n;++i){
        if(chk(dq)) answer++;
        dq.push_back(dq.front());
        dq.pop_front();
    }

    return answer;
}

C. 모두 0으로 만들기

각 정점에 가중치가 있는 트리가 주어진다. 연결된 두 정점을 골라 한쪽을 $1$ 증가시키고 다른 한쪽을 $1$ 감소시키는 연산을 할 수 있다. 트리의 모든 정점의 가중치를 $0$으로 만들 수 있는지, 만들 수 있다면 최소 몇 번의 연산이 필요한지 구하는 문제다.

Greedy하게 해결할 수 있다. 어떤 리프 노드의 가중치가 $c$일 때 이를 $0$으로 만들고 parent에 $c$를 넘겨주면, 이 리프 노드를 제외한 트리를 $0$으로 만드는 또다른 부분 문제가 된다. 이 때 각 연산은 교환 법칙이 성립하기 때문에 $c$번의 연산만 하면 된다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

#include <string>
#include <vector>

using namespace std;
using lint = long long;

int n;
lint b[300001];
vector<int> adj[300001];

lint go(int x,int p){
    lint ret = 0;
    for(auto to : adj[x])
        if(to != p)
            ret += go(to, x);
    ret += abs(b[x]);
    b[p] += b[x];
    return ret;
}

lint solution(vector<int> a, vector<vector<int>> edges) {
    n = a.size();
    for(int i=0;i<n;++i)
        b[i] = a[i];
    for(auto &e : edges){
        adj[e[0]].push_back(e[1]);
        adj[e[1]].push_back(e[0]);
    }
    lint ans = go(0,0);
    return b[0] == 0 ? ans : -1;
}

D. RPG와 쿼리

$n$개의 정점과 $m$개의 간선으로 이뤄진 가중치 그래프와 상수 $z$가 주어진다. 매 턴마다 움직이지 않고 $z$원을 얻거나, 연결된 정점으로 가면서 가중치 값인 $w$원을 얻거나, 어떤 도시든 순간이동하고 $0$원을 얻을 수 있다. 각 쿼리마다 $c$가 주어지는데, 정확히 $c$원을 모을 수 있는지, 모을 수 있다면 최소 몇 턴이 필요한지 구하는 문제다.

Dynamic Programming으로 해결할 수 있다. 다음과 같이 정의해보자.

    $dp[i][j]$ = $i$번 정점에 도달했을 때 $j$원을 들고 있는 경우, 필요한 최소 턴수

$i$는 최대 $3000$이지만 $j$는 최대 ${10}^{18}$이기 때문에 불가능하다. 대신 몇 가지 관찰을 통해 두 번째 차원의 크기를 줄일 수 있다. 정점을 적당히 이동하던 중에 모아야할 돈이 $z$의 배수만큼 남았다면 그 정점에 계속 있으면 된다. 모든 $w$는 $z$보다 작기 때문에 경로를 먼저 이동하면서 $x = c \ (\mathrm{mod} \ z)$인 $x$원을 모은 뒤, $z$원을 반복적으로 모으는 순서로 강제하자.

이제, 각 정점에서 도달할 때 $x = c \ (\mathrm{mod} \ z)$인 $x$원을 들고 있는 경우, 필요한 최소 턴 수만 구하면 된다. 여기서 또 하나의 관찰을 할 수 있는데, 여기 필요한 최소 턴 수는 $50$을 넘지 않는다. 턴 수가 $50$이 넘는다면 비둘기집 원리에 의해 $\mathrm{mod} \ z$한 값이 같은 순간이 두 번 존재하게 된다. 그 사이에서 $z+\cdots+z$ 원 만큼 얻은 것이므로 생략할 수 있기 때문이다. 따라서 $50$원 이하의 돈을 최대 $50$번 벌 수 있으므로 $dp[3000][50 \cdot 50]$이면 충분하다.

$2500$개의 상태마다 모든 간선을 돌면서 업데이트 해주면 되므로 $O((n+m) \cdot 2500)$에 dp 테이블을 채울 수 있다. 마지막으로 $mn[i] = \min (dp[0 \sim n-1][i])$로 전처리하면 각 쿼리를 $O(1)$에 답할 수 있다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

#include <string>
#include <cstdlib>
#include <cstring>
#include <vector>
void mmn(long long &x,long long y){ if(x==-1 || x>y) x = y; }

using namespace std;

int w[3000][3000];
vector<int> rev[3000];

long long dp[3000][2501], mn[2501];

vector<long long> solution(int n, int z, vector<vector<int>> roads, vector<long long> queries) {
    for(auto e : roads){
        rev[e[1]].push_back(e[0]);
        w[e[0]][e[1]] = e[2];
    }

    // solve
    memset(mn, -1, sizeof(mn));
    memset(dp, -1, sizeof(dp));
    mn[0] = dp[0][0] = 0;
    for(int i=1;i<n;++i) dp[i][0] = 1;
    for(int p=1;p<2501;++p){
        for(int i=0;i<n;++i)
            for(auto from : rev[i])
                if(p - w[from][i]>=0 && dp[from][p - w[from][i]]!=-1)
                    mmn(dp[i][p], dp[from][p - w[from][i]] + 1);

        if(p>=z && mn[p-z]!=-1)
            mmn(mn[p], mn[p-z]+1);
        for(int i=0;i<n;++i)
            if(~dp[i][p]) mmn(mn[p], dp[i][p]);
        for(int i=0;i<n;++i)
            if(~mn[p]) mmn(dp[i][p], mn[p] + 1);
    }

    vector<long long> answer;
    for(auto q : queries){
        long long ans = -1;
        if(q < 2501) ans = mn[q];
        else{
            long long i = 2500;
            for(;~i;--i) if(i%z == q%z) break;
            if(~mn[i]) ans = (q-i)/z + mn[i];
        }
        answer.push_back(ans);
    }
    return answer;
}
programmers