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

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

Dynamic Programming 너무 싫다. 문제해설을 보고나서 이해가 된다고 생각해 돌아서면 다시 까먹는다. 이번 대회 셋도 결국 Knapsack-problem이었는데, 쫄아서 못풀었다. 너무 화나났다. 이것도 인내해야하니...
이번 대회에서 얻어간 것은

1. 문자열 대소 비교 함수 만들기
2. Knapsack문제 제발 이해하고 문제 풀어보기.

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

A - AtCoder Quiz 2 (*6)

접기/펼치기

문제 설명
Atcoder 왕국에는 프로그래밍 능력을 측정하기 위한 검사가 진행중이다.

참여자는 최대 $100$점까지 얻을 수 있고, 각 점수에 따라 등급을 획득한다.

• Novice: 점수가 $0$보다 작지 않고, $40$보다 작다.
• Intermediate: 점수가 $40$보다 작지 않고, $70$보다 작다.
• Advanced: 점수가 $70$보다 작지 않고 $90$보다 작다.
• Expert: 점수가 $90$보다 작지 않다.

수아는 $X$점을 얻었다.

한 단계 높은 등급을 얻기 위해서 필요한 최소 점수를 구하라. 만약 수아가 Expert등급을 얻었다면 expert를 출력한다.

문제 해설
단순 조건문 문제이다. expert가 아닌 점수를 받았다면 그 점수 사이에 있는 등급의 상한값에서 그 점수를 빼면 된다.

정답 코드

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int x; cin >> x;
    if(0 <= x && x < 40) cout << 40 - x;
    else if(40 <= x && x < 70) cout << 70 - x;
    else if(70 <= x && x < 90) cout << 90 - x;
    else cout << "expert";
    return 0;
}

B - Maritozzo (*18)

접기/펼치기

문제 설명
영어 소문자로 이루어진 세 문자열 $S_1, S_2, S_3$이 주어지고, $1, 2, 3$으로 이루어진 문자열 $T$가 주어진다.

$T$에 있는 문자에 따라서 세 문자열을 이어 붙이고, 최종 결과 문자열을 출력하라.
즉 다음 지시를 만족하면 된다.

• 각 정수 $i (1 \le i \le |T|)$ 에 대해서 해당하는 다음과 같이 정해지는 문자열을 $s_i$라고 하자
  • 만약 $T$의 $i$번째 문자가 $1$이면 $S_1$
  • 만약 $T$의 $i$번째 문자가 $2$이면 $S_2$
  • 만약 $T$의 $i$번째 문자가 $3$이면 $S_3$
• 이 순서대로 문자열 $s_1, s_2, ..., s_{|T|}$를 붙이고 최종 결과 문자열을 출력하라.

문제 해설
$T$에 있는 문자가 각각 $1$이면 $S_1$을, $2$이면 $S_2$를, $3$이면 $S_3$을 그냥 순서대로 출력하면 된다.

정답 코드

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    string a, b, c; cin >> a >> b >> c;
    string s; cin >> s;
    for(auto x : s){
        if(x == '1') cout << a;
        else if(x == '2') cout << b;
        else cout << c;
    }
    return 0;
}

C - Neo-lexicographic Ordering (*260)

접기/펼치기

문제 설명
AtCoder왕국을 다스리는 수아는 영어 소문자 알파벳 순서를 바꾸기로 결정했다.

새로운 알아펫 순서는 $a, b, ..., z$로 이루어진 순열인 문자열 $X$로 나타낸다.
$X$의 $i$번째 문자 $(1 \le i \le 26)$은 새로운 순서의 $i$번째로 작은 소문자 순서이다.

이 왕국에는 이름이 $S_1, S_2, ..., S_N$인 $N$명의 시민이 있다. 각 이름 $S_i (1 \le i \le N)$은 영어 소문자로 이루어져 있다.

이 이름을 수아가 임의로 정한 순서대로 사전준으로 정렬하라.

문제 해설
그냥 이름을 모두 받고 새로운 기준으로 정렬을 수행하면 된다. 그러면 새로운 비교 함수인 compare을 작성해야 한다. 나는 lambda함수를 통해서 비교 함수를 만들었다.

일단 순서를 나타내는 배열 idx을 만들었다. 이 배열은 원래 알파벳 순서 (key)가 새로운 알파벳 순서인 (value)인 배열을 만들었다. 만약 알파벳 $k$가 $3$번째에 나왔다면 $k - 'a' = 3$이런 식으로 배열을 저장했다. 이때 $k - 'a'$를 하면 $k$가 알파벳 순서로 몇번째 있는지 나온다.

이제 비교 함수를 만들어야 하는데 이 비교함수는 다음과 같이 동작하며 c++의 string 연산자 오버로딩에도 사용돼기 때문에 알아두면 좋다.

1. 두 문자열 중 작은 문자열을 기준으로 반복문을 진행한다.
2. 서로 같은 위치에 있는 문자를 꺼내서 비교한다.
3. 만약 두 문자가 서로 다르다면 새로운 순서를 기록한 배열 idx를 기준으로 대소비교를 하고 그 결과를 return한다.
4. 끝까지 확인 했는데, 모든 문자가 같다면 두 문자열의 길이를 비교하고 더 작은 것이 있다면 그것을 정렬 우선순위로 한다.
5. 모두 같은 문자열이면 어느 순서도 상관 없기 때문에 고려 안해도 됀다.

정답 코드

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int idx[26];
    for(int i = 0; i < 26; i++){
        char c; cin >> c;
        idx[c - 'a'] = i;
    }

    int n; cin >> n;
    string a[n];
    for(auto& x : a) cin >> x;
    sort(a, a + n, [&idx](string& a, string& b){
        int len = min(a.size(), b.size());
        for(int i = 0; i < len; i++){
            if(a[i] != b[i]) return idx[a[i] - 'a'] < idx[b[i] - 'a'];
        }
        return a.size() < b.size();
    });

    for(auto x : a) cout << x << "\n";
    return 0;
}

D - Strange Lunchbox (*1085)

접기/펼치기

문제 설명
한 상점에는 $N$종류의 도시락을 팔고 있다. 한 종류에는 한 도시락이 있다.
각 $i = 1, 2, ..., N$에 대해서 $i$번째 도시락은 $A_i$개 타코야키와 $B_i$개 타이야키가 들어있다.

수아는 $X$개, 혹은 그 이상의 타코야키와 $Y$개, 혹은 그 이상의 타이야기를 먹고 싶다.
도시락 몇개를 골라서 최소 $X$개 타코야키와 최소 $Y$개 타이야키를 먹을 수 있는지 알고 싶다. 만약 가능하다면 수아가 반드시 사야하는 최소 도시락 개수를 알고 싶다.

단. 한 도시락을 1개 이상 살수는 없다.

문제 해설
그냥 딱 봐도 DP문제이다. 일단 제한도 모두 $300$보다 작고, 심지어 $X, Y, A_i, B_i$ 모두 $300$보다 작다. 얼핏 봤을 때 설마 3배열 dp겠어?라고 생각한 나에게 큰 엿을 선물했다. 정말 이걸로 푸는 것이다.

이 문제의 기본 골격은 knapsack문제이고 푸는 방법은 다음과 같다.
$dp[i][j][k]$ = (도시락을 $i$번째까지 확인 했을때, 타코야키 $j$개와 타이야키 $k$개를 먹을 수 있는 최소 도시락 개수) 이다.

일단 배열의 모든 수를 memset을 사용해서 INF로 초기화 한다. $dp[0][0][0] = 0$ 이라고 초기값을 설정한 다음, 다음 경우를 고려한다.

• $i$번째 도시락을 고르지 않을 경우: $dp[i + 1][j][k]$에 해당 개수인 $dp[i][j][k]$를 인계한다.
• $i$번째 도시락을 고르는 경우: $i$번째 도시락이 가지고 있는 타코야키와 타이야키의 개수인 $x, y$를 각각 $j, k$에 더한다. 이때 최대 $A_i, B_i$의 수는 $X, Y$이고 이 값을 넘으면 $X, Y$의 경우와 같기 때문에 min함수를 사용해서 상한값을 조정한다. $dp[i + 1][j + x][k + y]$에 해당 개수인 $dp[i][j][k] + 1$을 인계한다. $1$을 더한 이유는 $i$번째 도시락을 선택했기 때문이다. 주의할 점은 상한값을 조절해야 한다는 것이다.

모든 dp를 삼중 for문을 사용해서 확인하고 맨 마지막 결과를 확인해서 해당 개수가 $n$보다 크면 불가능하기 때문에 $-1$을 출력하고 그렇지 않으면 그 값을 출력한다.

정답 코드

#include <bits/stdc++.h>
using namespace std;

int dp[310][310][310];

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    memset(dp, 0x3f, sizeof(dp));
    int n; cin >> n;
    int X, Y; cin >> X >> Y;
    int a[n], b[n];
    for(int i = 0; i < n; i++) cin >> a[i] >> b[i];
    dp[0][0][0] = 0;

    for(int i = 0; i < n; i++){
        int x = a[i], y = b[i];
        for(int j = 0; j <= X; j++){
            int mx = min(j + x, X);
            for(int k = 0; k <= Y; k++){
                int my = min(k + y, Y);
                dp[i + 1][j][k] = min(dp[i][j][k], dp[i + 1][j][k]);
                dp[i + 1][mx][my] = min(dp[i + 1][mx][my], dp[i][j][k] + 1);
            }
        }
    }
    cout << (dp[n][X][Y] > n ? -1 : dp[n][X][Y]);
    return 0;
}