AtCoder Beginner Contest 201 - A부터 C까지 업솔빙

Mynavi Programming Contest 2021（AtCoder Beginner Contest 201） A부터 C까지 업솔빙

두번째로 풀어본 Atcoder 문제셋이다. A번 문제는 그냥 풀었지만 B번에서 push_back()을 안하고 정렬을 하다가 계속 에러나서 순간 머리가 지진나서 시간을 좀 끌었다. 그리고 C번 문제는 딱 코드포스 1100점짜리 문제인거 같은데, 1시간동안 못풀었지만 완전탐색에 있는 유형을 하나 일깨워줬다. 이번 대회를 참여하면서 배운 것은

1. 완전탐색을 항상 생각해 보는 자세

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

A - Tiny Arithmetic Sequence (*12)

접기/펼치기

문제 설명
3개의 정수로 이루어진 수열 $A=(A_1,A_2,A_3)$ 이 주어진다.
$A$의 원소를 재배열해서 등차수열을 만들 수 있는가?
다시 말해서 $A$의 원소를 재배열해서 $A_3-A_2=A_2-A_1$ 을 만족할 수 있는가?

제약

• $1\le A_i\le 100$
• 모든 입력은 정수다.

문제 해설
설명이 필요한가? 위 식을 정리하면 $2\cdot A_2=A_1+A_3$ 이 되고, $A_2$ 가 될수 있는 수는 3개이므로 모든 경우의 수를 시도해보고 하나라도 조건에 맞으면 YES를 출력하면 된다.

혹은 배열의 원소를 정렬하고 위에서 정리한 식에 맞으면 YES를 출력하는 방법도 있다.

정답 코드

#include <iostream>
using namespace std;

int main() {
    int a, b, c; cin >> a >> b >> c;
    cout << (2 * a == b + c || 2 * b == a + c || 2 * c == a + b ? "Yes" : "No");
    return 0;
}

B - Do you know the second highest mountain? (*32)

접기/펼치기

문제 설명
AtCoder공화국은 산이 $N$개 있다. $i$번째 산은 이름 $S_i$와 높이 $T_i$를 가지고 있다.

두번째로 높은 산의 이름을 출력하자. 모든 산은 모두 이름이 다르고, 모두 다른 높이로 주어진다.

제약

• $2\le N\le 1000$
• $1\le S_i$ 의 길이 $\le 15$
• $1\le T_i\le {10}^5$
• $S_i\ne S_j(i\ne j)$
• $T_i\ne T_j(i\ne j)$
• $S_i$는 영어 대문자와 영어 소문자, 그리고 정수로 이루어져 있다.ㅉ
• $N$과 $T_i$는 정수이다.

문제 해설
주어진 입력을 pair에 넣은다음 정렬을 하고, 배열에 뒤에서 2번째에 해당되는 $n-2$ 인덱스를 출력하면 된다. 이때 팁은 pair<string, int>으로 선언하면 이름순으로 정렬을 하기 때문에 새로 연산자 오버로딩 함수를 만들어야 한다. 따라서 pair<int, string>으로 선언해서 pair의 정렬기준을 높이로 하자.

정답 코드

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

int main() {
    int n; cin >> n;
    vector<pair<int , string>> v;
    for(int i = 0; i < n; i++){
        string s; cin >> s;
        int x; cin >> x;
        v.push_back({x, s});
    }
    sort(v.begin(), v.end());
    cout << v[n - 2].second;
    return 0;
}

C - Secret Number (*439)

접기/펼치기

문제 설명
지영이는 PIN넘버를 잊어버렸다. PIN은 $0,1,...,9$ 로 이루어진 4자라 문자열을 말하고, $0$으로 시작할 수 있다.

$0$ 부터 $9$ 까지 숫자에 대해 지영이는 다음 사실을 $10$ 자리 문자열 $S_0,S_1,...,S_9$ 로 표현하는 방식으로 기억한다.

• 만약 S_i가 'o': 지영이는 PIN넘버에 정수 i가 포함된다는 것을 확신한다.
• 만약 S_i가 'x': 지영이는 PIN넘버에 정수 i가 포함되지 않는다는 것을 확신한다.
• 만약 S_i가 '?': 지영이는 PIN넘버에 정수 i가 포함되는지 아닌지 확신하지 못한다.

지영이의 PIN넘버가 될 수 있는 문자열은 몇개나 있을까?

제약

• $S$는 문자 'o', 'x', '?'로 이루어진 $10$자리 문자열이다.

문제 해설
총 경우의 수가 $0$ 부터 $9999$ 까지라는 사실을 계속 놓치고 있었던 것이 내 실패 포인트였다고 생각한다. 총 경우의 수가 $10000$ 개 이므로 그냥 완전탐색 돌리면 되는 간단한 문제였는데, 이것을 경우의 수를 찾겠다고 난리를 치다가 포기한 문제였다. 근데 고수들 코드를 보니까 이걸 순열, 조합, 같은것을 포함하는 순열, 중복조합까지 싹다 동원해서 푼 사람이 있었다.....

$0$부터 $9999$까지 될 수 있는 모든 경우의 수에서 위에 말한 제약 사항을 모두 만족하는 수만을 세면 문제를 풀 수 있다. 여기서 주의해야할 점은

1. PIN넘버는 무조건 4자리이기 때문에 자릿수를 반드시 4번을 따야한다.
2. $i$가 존재해야하는데 자릿수에 없거나, $i$가 존재하면 안되는데 자릿수에 존재하면 바로 개수를 카운팅하지 않는 조건문을 깔끔하게 작성해야한다.

정답 코드

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

int main() {
    char digit[10];
    for(int i = 0; i < 10; i++) cin >> digit[i];
    int ans = 0;
    for(int i = 0; i < 10000; i++){
        int tmp = 4, num = i;
        bool cnt[10] = {};
        while(tmp--){
            cnt[num % 10] = true;
            num /= 10;
        }

        bool flag = true;
        for(int i = 0; i < 10; i++){
            if(digit[i] == 'o' && !cnt[i]) flag = false;
            if(digit[i] == 'x' && cnt[i]) flag = false;
        }
        if(flag) ans++;
    }
    cout << ans;
    return 0;
}