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

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

일본 친구들은 진짜 DP를 좋아하는 것 같다. C번 문제는 문자열 DP에, D번 문제는 BFS + 다익스트라 + DP문제를 내놓았다. 코드포스에서는 민트까지 DP가 거의 안나오는데, atcoder에서 높은 티어를 받으려면 dp를 무조건적으로 정복해야 할 것같다. 다행인거는 전형적인 dp가 맨날 나온다는 점? 문제 유형 다 외워버려야지.. 이번 대회에서 배운 점은

1. 문자열 dp
2. 다익스트라는 결국 BFS의 변형이다.
3. 최단 경로 개수 찾기

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

A - Blood Pressure (*6)

접기/펼치기

문제 설명
사람의 수축기 혈압인 $A$가 주어진다. 그리고 이완기 혈압인 $B$가 주어진다.
사람의 평균 동맥 혈압 $C$를 구하시오. 평균 동맥 혈압은 다음과 같이 주어진다.

• $C = \frac{A - B}{3} + B$

문제 해설
그냥 식대로 코드 작성하면 됩니다. 소숫점 자리 맞추는 것만 주의하면 된다.

정답 코드

#include <iostream>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    double a,b; cin >> a >> b;
    cout.precision(6);
    cout << fixed << (a - b) / 3 + b;
    return 0;
}

B - Cycle Hit (*17)

접기/펼치기

문제 설명
문자열 4개 $S_1, S_2, S_3, S_4$ 가 주어진다.
이 문자열들이 H, 2B, 3B, HR을 각각 하나씩 포함하고 있는지 판별하시오.
모든 $S_i$들은 H, 2B, 3B, HR 로만 주어진다.

문제 해설
모든 $S_i$들은 H, 2B, 3B, HR 로만 주어진다. 이 문장을 놓쳐서 조금 뇌절할 뻔한 문제였다. 내가 생각한 방법은 set에 주어진 4개의 문자열을 넣고 $S_i$가 주어질 때 마다 set에서 원소가 존재하는지 확인하고, 존재하면 그 문자열을 set에서 제거한다. 최종적으로 set에 원소가 남아있지 않으면 모든 4개의 문자열이 하나씩 있다는 뜻이고 원소가 남아있다면 중복되는 문자열이 있다는 뜻이다.

정답 코드

#include <iostream>
#include <set>
#include <string>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    set<string> s;
    s.insert("H");
    s.insert("HR");
    s.insert("2B");
    s.insert("3B");
    for(int i = 0; i < 4; i++){
        string str; cin >> str;
        if(s.find(str) != s.end()) s.erase(str);
    }
    cout << (s.size() > 0 ? "No" : "Yes");
    return 0;
}

C - chokudai (*559)

접기/펼치기

문제 설명
문자열 $S$가 주어진다.

문자열 $S$의 왼쪽에서 오른쪽으로 읽을 때 c, h, o, k, u, d, a, i로 읽을 수 있는 경우의 수는 몇개일까?

이 값은 매우 크기 때문에 값을 $(10^9 + 7)$ 로 나눈 나머지를 출력한다.

문제 해설
일본 친구들은 dp를 너무 너무 너무 좋아한다. 이 문제를 재귀형식으로 풀어보려 했는데 시간초과가 나는 것을 보고 다른 방식이 있다는 것을 생각했어야 하는데 너무 안일했다.
dp문제는 풀이 방법이 정해져있어서 방법을 모르면 절대 못풀지만 반대로 말하면 풀이 방법만 알면 반드시 풀 수 있다는 뜻이니까 방법을 익혀보자.

chokudai문자열을 $A$라고 하면 우리는 dp배열을 다음과 같이 정의한다.

• $dp(i, j)$ = 문자열 $S$의 $j$번째 문자까지 사용했을 때, $A[0:i]$ substring을 만들 수 있는 경우의 수.

이렇게 정의하면 우리가 원하는 값은 $dp(8, N)$ 에 있을 것이다.

일단 $i = 0$인 경우는 어떨까? 문자열 $S$를 아무리 뒤져봐도 공백 스트링을 만들 수 있는 경우는 반드시 1가지이다. 따라서 $i = 0$인 줄은 모두 1로 채우면 된다.
반대로 $j = 0$인 경우는 어떨까? $i = j = 0$ 인 경우를 빼고는 $S$의 공백 스트링으로 $A$ substring을 만들 수 있는 경우는 없기 때문에 모두 0으로 채우면 된다.

이제 결국 남은 경우의 수는 2가지이다.

• $A[i] \neq S[j]$ 인 경우: 이 문자로는 $A[0:i]$를 만들 수 없기 때문에 이전에 있는 결과인 $dp[i][j - 1]$ 값을 그대로 한다.
• $A[i] = S[j]$ 인 경우: 2가지 경우의 수가 있다.
  • $A[i]$를 사용하는 경우: 그렇다면 남은 $A[0:i - 1]$문자열을 $j - 1$번째 문자열까지 봐서 얻을 수 있는 경우의 수를 구해야한다. 따라서 이 경우는 $dp[i - 1][j - 1]$이 필요하다.
  • $A[i]$를 사용하지 않는 경우: 위에서 말한 $A[i] \neq S[j]$ 이거랑 똑같기 때문에 $dp[i][j - 1]$ 값이 필요하다.

즉 점화식은 다음과 같다.

• $(A[i] \neq S[j])$ $dp[i][j] = dp[i][j - 1]$
• $(A[i] = S[j])$ $dp[i][j] = dp[i][j - 1] + dp[i - 1][j - 1]$

이대로 코드 작성하면 되고 값을 $10^9 + 1$로 나눈 나머지를 구해야하기 때문에 매 덧셈 연산마다 저 값을 나누어줘야 한다.

정답 코드

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

typedef long long ll;
const int mod = 1e9 + 7;
ll dp[9][100002];

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    string s; cin >> s;
    string a = "chokudai";
    int len = s.size();
    for(int i = 0; i <= len; i++) dp[0][i] = 1;
    for(int i = 1; i <= 8; i++){
        for(int j = 1; j <= len; j++){
            dp[i][j] = dp[i][j - 1];
            if(a[i - 1] == s[j - 1]) dp[i][j] = (dp[i][j] + dp[i - 1][j - 1]) % mod;
        }
    }
    cout << dp[8][len];
    return 0;
}

D - Number of Shortest paths (*755)

접기/펼치기

문제 설명
타카하시 왕국에는 도시 $N$개와 도로 $M$개가 있다. 도시는 $1$부터 $N$까지 번호가 붙여져 있고 도로는 $1$부터 $M$까지 번호가 붙여져 있다.

도로 $i$를 사용하면 도시 $A_i$ 부터 $B_i$까지 혹은 그 반대로도 $1$시간 걸린다.

도시 $1$부터 $N$까지 가는 최단 경로의 개수는 몇개인가?

이 값은 매우 크기 때문에 값을 $(10^9 + 7)$ 로 나눈 나머지를 출력한다.

문제 해설
일단 최단경로 문제인데 모든 도시의 가중치가 1인것을 보고 이 문제는 BFS를 사용해야하는 것은 전제로 들어갔다. 그리고 $N$과 $M$의 수가 너무 크기 때문에 플로이드-와샬 알고리즘은 사용하면 안될 것 같다는 생각을 했다. 그러면 어떻게 이 문제를 풀까? 답은 우리가 고등학교때 최단거리의 개수를 구하는 방식을 사용하면 된다.

이 문제를 기억하는가? 우리가 중학교, 고등학교때 풀었던 최단경로 경우의 수 구하는 문제를 풀때 이렇게 풀었을 것이다. 이 방법을 그래프에도 동일하게 적용할 수 있다.

BFS를 사용하는 것은 같지만 추가로 2개의 배열이 더 필요하다. $1$부터 $V$까지 최단 거리를 저장해 놓는 $dist$배열, $1$부터 $V$까지 최단 거리의 개수를 저장해 놓는 $cnt$배열이다.

다익스트라는 가중치가 서로 다르기 때문에 dist배열을 사용하는데, bfs도 결국은 가중치가 1인 다익스트라 알고리즘과 같다. 따라서 방법은 다음과 같이 하면 된다.

1. BFS를 사용해서 아직 최단 거리가 갱신이 안된 노드에 도착했을 때 최단거리를 현재 노드의 거리 + 1로 갱신해 준다. 그리고 개수는 현재 노드에 있는 값을 그대로 이어 받는다.

2. 최단 거리가 갱신이 된 노드에 도착했을 때, 이 노드로 가는 것이 최단경로인지 아닌지 확인을 해야한다.

   • 최단 경로라는 것을 어떻게 판단할까? BFS적 관점으로 생각해 보면 다음 Level로 이동을 해야 최단거리로 이동했다고 할 수 있다. 같은 Level로 이동하면 한번 돌아서 가는 것이기 때문에 최단 경로가 아니기 때문이다.

   • 따라서 dist[다음 노드] = dist[현재 노드] + 1인 경우 이 노드로 가는 것이 최단 경로이기 때문에 개수를 갱신해 준다. 현재 있는 최단거리 개수에 추가로 개수를 더해서 이 노드로 가는 방법이 추가로 더 있다는 것을 알려주는 방식으로 cnt배열을 사용한다. 이 방법은 위에서 말했던 최단거리 경우의 수를 구하는 법과 일치하다.

정답 코드

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

typedef long long ll;
const int mod = 1e9 + 7;

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

    queue<int> q;
    q.push(1), dist[1] = 0, cnt[1] = 1;
    while(q.size()){
        int cur = q.front();
        q.pop();
        for(auto x : g[cur]){
            if(dist[x] == -1){
                dist[x] = dist[cur] + 1;
                cnt[x] = cnt[cur];
                q.push(x);
            }else{
                if(dist[x] == dist[cur] + 1) cnt[x] = (cnt[x] + cnt[cur]) % mod;
            }
        }
    }
    cout << cnt[n];
    return 0;
}