AtCoder Beginner Contest 204 - A부터 D까지 업솔빙

AtCoder Beginner Contest 204 A부터 D까지 업솔빙

atcoder의 문제 수준에 갈수록 놀라면서 문제를 풀고 있다. 확실히 플랫폼이 달라서 그런지 출제되는 문제 유형도 확연하다고 느낀다. 하지만 여기서 배운 방식을 codeforces에서 쓸 수 있을 것 같다는 생각이다. 근데 codeforces에서 푼 문제는 글쎄? atcoder에서 쓸 수 있을까? 아직은 dp가 어렵기 때문에 그것은 지켜봐야할 문제인 것 같다.
이번 대회를 참여하면서 배운 것은

1. 냅색 알고리즘의 변형 문제

문제 옆에 붙어있는 난이도는 Atcoder Problems 에서 추정한 것으로 작성했다는 것을 미리 알린다.

A - Rock-paper-scissors (*7)

접기/펼치기

문제 설명
사과, 오렌지, 포도는 가위바위보를 하고 있고, 이 결과를 비기고 싶다.

오렌지와 포도가 낸 패를 의미하는 문자 $x$, $y$가 주어진다.
각각 $0$은 바위, $1$은 가위, $2$는 보자기를 의미한다.

사과가 내야하는 문자를 출력하자.

제약

• 각 $x$, $y$는 $0$과 $1$과 $2$로 이루어져 있다.

문제 해설
$x=y$ 이면 같은 값을 내면 비기고, $x\ne y$ 이면 두 사람이 낸 패와 다른 걸 내면 된다.

정답 코드

#include <iostream>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int a, b, c; cin >> a >> b >> c;
    cout << 21 - (a + b + c);
    return 0;
}

B - Nuts (*9)

접기/펼치기

문제 설명
나무 $N$가 있고, $i$번째 나무에는 땅콩 $A_i$개가 열렸다.

병건은 나무에서 다음과 같은 방식으로 땅콩을 수확하고 싶다.

• 나무에 $10$개 혹은 그보다 작은 땅콩이 열리면 그 나무에 열린 땅콩을 수확하지 않는다.
• 나무에 $10$개 보다 많은 땅콩이 열리면 전체 땅콩을 수확하지만 $10$개는 남긴다.

병건이가 수확해야하는 땅콩의 총 개수를 구하자.

제약

• $1\le N\le 1000$
• $0\le A_i\le 1000$
• 모든 입력은 정수로 이루어져 있다.

문제 해설
설명이 필요한가? 배열에 있는 모든 값을 순회하면서 그 값이 10보다 큰 경우에만 그 값에 10을 뺀 결과를 더하면 된다.

정답 코드

#include <iostream>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n; cin >> n;
    int ans = 0;
    for(int i = 0; i < n; i++){
        int num; cin >> num;
        if(num > 10) ans += num - 10;
    }
    cout << ans;
    return 0;
}

C - Tour (*629)

접기/펼치기

문제 설명
Atcoder 공화국에 $1$ 부터 $N$까지 번호를 가지고 있는 도시 $N$개가 있고 $1$ 부터 $M$까지 번호가 부여된 $M$개의 도로가 있다.

$i$번 도로는 도시 $A_i$부터 $B_i$까지 이어져 있지만 $B_i$에서 $A_i$로 이동할 때는 이용할 수 없다.

퓨마는 어느 한 도시에서 여행을 시작하려고 계획하고 있다. 여행은 도로를 하나도 안쓰거나 수많은 도로를 사용할 수 있다.

퓨마의 여행의 시작과 끝으로 이루어진 도시의 집합쌍이 몇개나 있을까? 같은 집합이라도 다른 순서로 이루어져 있으면 다른 쌍이라고 구별한다.

제약

• $2\le N\le 2000$
• $0\le M\le min(2000,N(N-1))$
• $1\le A_i,B_i\le N$
• $A_i\ne B_i$
• $(A_i, B_i)은 구별된다.
• 모든 값은 정수로 주어진다.

문제 해설
처음 볼 때 그래프 문제라는 것을 알았는데, 문제를 읽어보고 그림을 그려보니까 생각보다 간단한 문제라는 것을 알았다. 이 문제를 풀면서 출제자가 물어보고 싶은게 뭔지 알았다.

너 DFS는 아니? 이 질문과 동의어 였기 때문에 그냥 나는 쉽게 문제를 풀었다.

그래프 탐색인 DFS와 BFS모두 한곳을 출발점으로 해서 갈수 있는 모든 정점을 탐색하는 방식이기 때문에 한 노드에서 시작할 때 DFS 함수를 호출하는 횟수만 세줘도 문제에서 요구하는 정점 쌍을 다 구할 수 있다.

이 문제가 어렵게 느껴지는 사람은 그래프 탐색의 기초를 배우고 오자. 그러면 쉽게 풀 수 있다.

정답 코드

#include <iostream>
#include <vector>
using namespace std;

vector<int> g[2001];
vector<bool> visit;
int ans = 0;

void dfs(int x){
    visit[x] = true;
    ans++;
    for(int i = 0; i < g[x].size(); i++){
        int next = g[x][i];
        if(!visit[next]) dfs(next);
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n, m; cin >> n >> m;
    while(m--){
        int u, v; cin >> u >> v;
        g[u].push_back(v);
    }

    for(int i = 1; i <= n; i++){
        visit = vector<bool>(n + 1);
        dfs(i);
    }
    cout << ans;
    return 0;
}

D - Cooking (*832)

접기/펼치기

문제 설명
철수는 $1$ 부터 $N$까지 번호가 부여된 접시 $N$개를 요리할 것이다.

접시 $i$는 오븐에서 $T_i$분 조리해야 완성된다. 두개 혹은 더 많은 접시를 동시에 요리할 수 없다.

만약 철수가 두 오븐을 사용한다면 모든 $N$개의 접시를 요리할 때 필요한 최소 시간 값이 무엇일까? 모든 오븐에 접시를 넣고 접시를 빼는 모든 행위에서 걸리는 시간은 무시한다.

제약

• $1\le N\le 100$
• $1\le T_i\le {10}^3$

문제 해설
다이나믹 프로그래밍 인지 감도 안잡혀서 업솔빙을 하면서 DP문제라는 것을 깨달았다. 결론 부터 말하자면 이 문제는 0-1 냅색 알고리즘을 사용해서 푼다. 그런데 이 알고리즘에는 DP로 푸는 방식도 있는데, 그리디한 방법으로 푸는 경우도 있었고 내가 처음에 이 문제를 만났을 때 그리디한 방법으로 풀었다. 하지만 이 방식은 테스트 케이스 조금만 생각해보면 답이 아니라는 것을 바로 알기 때문에 다른 방법으로 선회 했어야 한다. 하지만 나는 이 냅색 알고리즘이 아직도 헷갈리고 어려웠기 때문에 생각하기 쉽지 않았다. 계속 이와 비슷한 알고리즘을 사용하는 문제를 풀어보면서 숙달해야겠다.

이 문제가 왜 DP를 사용하는 문제일까? 꼼수를 써보면 일단 문제 조건이 그리디를 사용하기에는 너무 작다는 것이 첫번째 이유다. 그리디를 사용하려면 최대한 시간이 빡빡하게 나올 텐데 이 문제는 최대 경우가 100000으로 엄청 작다. 그리고 이 문제는 결국 $i$번째 요리가 등장할때 이 요리를 오븐에 넣어? 말어? 를 결정하는 문제이고 이 모든 경우는 최대 $2^{100}$ 이기 때문에 완전탐색으로 하기에는 말이 안된다. 따라서 공간 복잡도를 희생해서 빠른 시간을 갖는 다이나믹 프로그래밍을 그 와중에 $i$번째 요리가 등장할때 이 요리를 오븐에 넣어? 말어? 를 결정하는 문제를 풀 수 있는 0-1 냅색 알고리즘을 사용한다.

계속 오븐이 1개 있다고 가정을 하는데, 오븐이 1개있다고 할 때 다른 오븐에 넣는 시간은 상관 없다. 왜냐하면 첫번째 오븐이 요리를 하는데 사용하는 총 시간이 $A$이고 전체 요리가 완성되는 시간이 $S$라고 하면 두번째 오븐이 요리를 하는데 걸리는 시간이 $S-A$ 이기 때문이다. 따라서 하나의 오븐이 걸리는 시간을 구하면 자동으로 두번째 오븐이 걸리는 시간을 구할 수 있고 우리는 $max(A,B)$ 값을 최소화 하는 것이 목적이다.

0-1 냅색 알고리즘은 DP를 이렇게 정의한다.

• $dp(i,j)$ = 요리를 $i$번째 까지 고려했을 때 $j$분이 걸릴 수 있는가? true or false

그리고 이 알고리즘에서 $i$번째 요리를 선택하지 않는다면 $dp(i,j)=dp(i-1,j)$ 이다. 왜냐하면 $i$번째 요리를 선택하지 않기 때문에 $i-1$번째 요리를 선택한 상황과 같기 때문이다.
반면에 $i$번째 요리를 선택한다면 $dp(i,j)=dp(i-1,j-A_i)$ 이다. 왜냐하면 $i$번째 요리가 걸리는 시간이 $A_i$라면 이 요리가 걸리는 시간을 뺀 시간을 $i-1$까지 고려했을 때 경우를 생각해야 하기 때문이다. $dp(i-1,j-A_i)$ 가 true이면 이 요리를 선택해서 $A_i$시간을 사용할 수 있다는 뜻이다. 만약 false이면 $i-1$번째 요리를 조리 했을 때 $j-A_i$ 시간이 걸리는 경우 자체가 없기 때문에 $i$번째 요리를 했을 때 $j$시간이 걸리는 경우의 수 자체가 없다.

만약 $j<A_i$ 이면 $i$번째 요리를 넣는 순간 $j$의 값을 벗어나기 때문에 반드시 요리를 넣을 수 없고, 그냥 이전 요리의 결과값을 계승한다.
하지만 $j>=A_i$이면 $i$번째 요리를 넣을까? 말까?를 고민해야 하므로 요리를 넣지 않는 경우인 $dp(i-1,j)$ 와 요리를 넣는 경우인 $dp(i-1,j-A_i)$사이의 or 연산을 해서 둘중에 하나라도 되는 경우가 있으면 1을 저장한다.

마지막으로 모든 요리를 수행했을 때 가능한 시간이 $dp[n][i]$에 모여있는데, 모든 $i$값에 대해서 요리를 $i$분 걸릴 수 있을 때 최솟값을 비교하면 답이 나온다.

정답 코드

#include <iostream>
#include <numeric>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n; cin >> n;
    int arr[n];
    for(int& i : arr) cin >> i;
    bool dp[n + 1][100001] = {};
    dp[0][0] = true;
    int sum = accumulate(arr, arr + n, 0);

    for(int i = 0; i < n; i++){
        for(int j = 0; j <= 100000; j++){
            if(j >= arr[i]) dp[i + 1][j] = dp[i][j] | dp[i][j - arr[i]];
            else dp[i + 1][i] = dp[i][j];
        }
    }

    int ans = 987654321;
    for(int i = 0; i <= 100000; i++){
        if(dp[n][i]) ans = min(ans, max(i, sum - i));
    }
    cout << ans;
    return 0;
}