[C++] code jam 2020 Qualification Round

0. [C++] code jam

https://codingcompetitions.withgoogle.com/codejam/round/000000000019fd27

1. 풀이

1. Vestigium

이 문제는 'Latin square'를 분석하는 문제였다. 이에 대한 관련 글은 검색을 통해 알아보았는데, 간단하게 N*N의 배열에 가로 세로줄에 중복되지 않는 1~N까지의 수를 배치하는 배열이다.

이 문제에서 출력으로 Case #x: k r c를 출력해야 하는데, k는 대각선의 총 합, r은 가로줄에서 오류가 있는 줄의 총 합, c는 세로줄에서 오류의 총 합을 출력하면 된다.

이 문제의 풀이는 간단하게 모든 수를 방문하는 것으로 풀이하였다. bool 배열을 만들어서 각 줄의 중복을 관리하고, 중복이 발생하면 카운트를 해주며 다음 줄을 탐색하는 방식을 택하였다.

2. Nesting Depth

이 문제는 입력된 숫자에 맞게 자신의 좌 우에 괄호 쌍이 존재해야하는 문제였다.

Case #1: 0000
Case #2: (1)0(1)
Case #3: (111)000
Case #4: (1)

이와 같은 결과를 얻기 위해서 간단하게 입력을 string에 담고, string을 순서대로 따라가면서 현재 숫자의 입력에서 필요한 괄호의 개수만큼 그때 그때 괄호를 string에 추가해주는 방식을 택해주었다. 마지막으로 괄호를 닫는 과정은 코드에 주석으로 설명해놓았으니 코드를 읽어보시면 이해할것이라 생각하고 생략.

3. Parenting Partnering Returns

이 문제는 생각보다 너무 간단한데, 출력에서 시간 순서와 별개로 'C', 'J'를 입력 순서로 출력해주었어야 하는 부분이 틀린것을 알아차리는데까지 시간이 오래걸렸다.

이 문제를 해결하기 위해 pair<int, int> 활용을 통해 해결해주었다.

추가적으로 문제를 빠르게 해결하기 위해 input을 vector에 저장하여 시간순서대로 정렬해주었고, Cameron과 Jamie를 배치하는데 두명중 시간이 자유로운 사람을 우선적으로 배치하는 방식을 택해주었다. 또한 배치가 불가능한 경우라면, 탐색을 종료하고 IMPOSSIBLE을 출력하도록 코드를 구현해주었다.

4. ESAb ATAd

ㅎㅎ 문제를 이해하지 못했다... 이는 이후에 추가적으로 공부해보자.

문제를 다시 보면서 다른 사람의 코드를 읽는 것이 가능하던데, 혹시 이 글을 읽으시는 분이 계신다면 참고되셨으면 좋겠네요.

5. Indicium

이 문제는 1번 문제의 확장판이라 보면 된다.

각 줄에 숫자가 겹치지 않게 배치하는 과정에서 bfs, dfs를 활용하면 될 것이라고 예상은 하지만, 실제 구현은 실패하였다.

2. 소스코드

1.

#include<iostream>
#include<algorithm>
 
using namespace std;
 
int T, N;
int arr[101][101];
 
pair<int, int> calc() {
    pair<int, int> ret = { 0,0 };
    for (int i = 0; i < N; i++) {
        bool row[101] = { false };
        bool col[101] = { false };
        bool flag_row = false;
        bool flag_col = false;
        for (int k = 0; k < N; k++) {
            if (!row[arr[i][k]]) {
                row[arr[i][k]] = true;
            }
            else {
                if (!flag_row) {
                    ret.first++;
                    flag_row = true;
                }
            }
            if (!col[arr[k][i]]) {
                col[arr[k][i]] = true;
            }
            else {
                if (!flag_col) {
                    ret.second++;
                    flag_col = true;
                }
            }
        }
    }
 
    return ret;
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    cin >> T;
    for (int i = 1; i <= T; i++) {
        cin >> N;
        for (int j = 0; j < N; j++) {
            for (int k = 0; k < N; k++)
                cin >> arr[j][k];
        }
        int sol = 0;
        for (int j = 0; j < N; j++)
            sol += arr[j][j];
        pair<int, int> ret = calc();
 
        cout << "Case #" << i << ": " << sol << " " << ret.first << " " << ret.second << "\n";
    }
 
    return 0;
}

2.

#include<iostream>
#include<algorithm>
#include<string>
 
using namespace std;
 
int T;
string S;
 
void calc() {
    int num = 0;
    int this_num = 0;
    for (int i = 0; i < S.size(); i++) {
        if (S[i] >= '0' && S[i] <= '9') {
            this_num = S[i] - '0';
            //만일 이전 수보다 더 큰 수가 들어왔다면, '('를 추가로 입력해준다.
            if(num < this_num)
                for (int k = 0; k < this_num - num; k++) {
                    S.insert(i, 1, '(');
                }
            //만일 더 작은 수라면, 앞에 차이만큼 ')'를 입력해준다.
            else {
                for (int k = 0; k < num - this_num; k++) {
                    S.insert(i, 1, ')');
                }
            }
                num = this_num;
        }
    }
    for (int i = 0; i < this_num; i++) {
        S.push_back(')');
    }
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    cin >> T;
    for (int i = 1; i <= T; i++) {
        cin >> S;
 
        calc();
 
        cout << "Case #" << i << ": " << S << "\n";
    }
 
    return 0;
}

3.

#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
 
using namespace std;
 
int T, N;
vector<pair<pair<int, int>, int> > V;
int arr[1001];
 
bool calc() {
    int end_C=0, end_J=0;
    for (int i = 0; i < V.size(); i++) {
        if (end_C <= V[i].first.first) {
            arr[V[i].second] = 1;
            end_C = V[i].first.second;
        }
        else if (end_J <= V[i].first.first) {
            arr[V[i].second] = 2;
            end_J = V[i].first.second;
        }
        else {
            return false;
        }
    }
    return true;
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    cin >> T;
    for (int i = 1; i <= T; i++) {
        cin >> N;
        V.clear();
        int temp1, temp2;
        for (int k = 0; k < N; k++) {
            cin >> temp1 >> temp2;
            V.push_back({ {temp1, temp2}, k });
        }
        sort(V.begin(), V.end());
        if (calc()) {
            cout << "Case #" << i << ": ";
            for (int k = 0; k < N; k++) {
                if (arr[k] == 1)
                    cout << 'C';
                else
                    cout << 'J';
            }
            cout << "\n";
        }
        else {
            cout << "Case #" << i << ": IMPOSSIBLE\n";
        }
    }
 
    return 0;
}

3. 참고

구종만, 「프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략」, 인사이트, 2012, p.216~236.

질문이나 지적 있으시면 댓글로 남겨주세요~

도움 되셨으면 하트 꾹!