2023 HPEC(Hanyang Programming Evaluation Contest) - Beginner Open

https://www.acmicpc.net/contest/view/1129

2023 HPEC(Hanyang Programming Evaluation Contest) - Beginner Open

코테 대비해서 대회셋을 풀어봤다.

 

A - 학번을 찾아줘!

간단한 사칙연산, 구현 문제였다. 문제에서 하라는 대로 하면 된다.

#include <iostream>
#include <cmath>
using namespace std;
long long arr[5];
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int t; cin >> t;
    for (int i = 0; i < t; i++) cin >> arr[i];

    long long ans = 0;

    ans += arr[0] > arr[2] ? abs(arr[0] - arr[2]) * 508 : abs(arr[0] - arr[2]) * 108;
    ans += arr[1] > arr[3] ? abs(arr[1] - arr[3]) * 212 : abs(arr[1] - arr[3]) * 305;
    ans += arr[4] * 707;
    ans *= 4763;
    cout << ans;

}

 

B - 너의 수능 점수가 궁금해

A번에서 반대과정을 하면된다.

Case-Work식으로 n에 4763을 나누고 문제에서 말하는 4가지 경우 모두 대조해보면 된다.

#include <iostream>
#include <cmath>
#include <vector>
using namespace std;
long long arr[5];
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int s; cin >> s;

    if (s % 4763 != 0) {
        cout << 0 << "\n";
        return 0;
    }

    s /= 4763;
    vector<pair<int, int>> ans;
    for (int i = 0; i <= 200; i++) {
        for (int j = 0; j <= 200; j++) {
            if (i * 508 + j * 212 == s) ans.push_back({ i, j });
            else if (i * 508 + j * 305 == s) ans.push_back({ i, j });
            else if (i * 108 + j * 212 == s) ans.push_back({ i, j });
            else if (i * 108 + j * 305 == s) ans.push_back({ i, j });
        }
    }

    if (ans.size() == 0) cout << 0;
    else {
        cout << ans.size() << "\n";
        for (pair<int, int> a : ans) cout << a.first << " " << a.second << "\n";
    }
}

 

C - 아니 이게 왜 안 돼

간단한 그리디 문제이다. H, Y, U가 나오지 않는 구간을 확인하고, M * D와 안 나온 구간 * D 중 작은 값으로 더하면 된다.

그리거 H, Y, U의 개수를 카운트하여 가장 작은 값으로 계산해주면 끝.

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

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n; cin >> n;
    string s; cin >> s;
    int d, m; cin >> d >> m;
    map<char, int> mp;
    int cnt = 0;
    int ans = 0;
    for (int i = 0; i < n; i++) {
        if (s[i] == 'H' || s[i] == 'Y' || s[i] == 'U') {
            if(cnt > 0) ans += min(m + d, d * cnt);
            cnt = 0;
            mp[s[i]]++;
        }
        else {
            cnt++;
        }
    }
    if(cnt > 0) ans += min(m + d, d * cnt);
    if (ans == 0)cout << "Nalmeok\n";
    else cout << ans << "\n";

    int mi = min({ mp['H'], mp['Y'], mp['U'] });

    if (mi == 0) cout << "I love HanYang University";
    else cout << mi;
}

 

D - 최애의 팀원

간단한 큐 문제.

순서대로 큐에 넣고 학번 만큼 빼고, 넣으면서 최종적으로 큐에 1개가 남을 때까지 반복한다.

N의 값이 최대 1000이고 학번도 최대가 2자리이기에 충분히 가능하다

#include <iostream>
#include <queue>
#include <string>
using namespace std;
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n; cin >> n;
    queue<pair<string, int>> q;
    for (int i = 0; i < n; i++) {
        string s; int k; cin >> s >> k;
        q.push({ s, k });
    }

    while (q.size() > 1) {
        pair<string, int> now = q.front();
        q.pop();

        for (int i = 0; i < now.second - 1; i++) {
            pair<string, int> k = q.front();
            q.pop();
            q.push(k);
        }
        q.pop();
    }
    cout << q.front().first;
}

 

F - 배신자

생각보다 애먹은 문제이다. 풀이는 간단하다. 배신자에서 출발하여 dfs를 돈다. dfs를 돌면서 사이클이 생기면 이때까지 정점을 카운트한 것에다 -1을 해준다.  그리고 배신자 그룹 말고, 아예 연결되지 않은 그룹이 있을 수 있기에 방문처리 한 배열을 이용하여 남은 그룹까지 체크해준다. 

이 문제는 bfs가 불가능하다. 왜냐하면, 그룹을 체크할 때 만약 한 정점이 2개 이상의 간선을 가진다면 그룹 내에 정점 개수를 체크하는게 많이 힘들어지기에 dfs를 사용해야한다.

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

bool visited[200001];
vector<vector<int>> list(200001);
int s;
long long ans = 0;
int check = -1;
long long DFS(int now, int before, int s, bool isCheck) {
    if (isCheck) {
        for (int next : list[now]) {
            if (visited[next]) {
                if (next == s && before != s && check == -1) {
                    check = now;
                    continue;
                }
            }
        }
    }
    long long depth = 1;
    for (int next : list[now]) {
        if (visited[next]) continue;
        visited[next] = true;
        if (now == s && isCheck) {
            ans = max(DFS(next, now, s, isCheck) + 1, ans);
            check = -1;
        }
        else {
            depth += DFS(next, now, s, isCheck);
            ans = max(depth, ans);
        }
    }
    if (now == check) return depth - 1;
    return depth;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n, m; cin >> n >> m;
    
    for (int i = 0; i < m; i++) {
        int a, b; cin >> a >> b;
        list[a].push_back(b);
        list[b].push_back(a);
    }
    cin >> s;
    visited[s] = true;
    DFS(s, 0,  s, true);
    for (int i = 1; i <= n; i++) {
        if (visited[i]) continue;
        visited[i] = true;
        DFS(i, 0, i, false);
    }
    if (n == 1) cout << 1;
    else  cout << ans;

}

 

G - 지각하기 싫어

개인적으로 이번 셋에서 가장 재밌었던 문제

먼저 애지문에서 대운동장까지의 Map과 Set, 대운동장에서 ITBT관까지의 Map과 Set을 선언해준다.

그리고 입력으로 들어오면 map과 set에 그 정보를 넣어준다.

그리고 연산에서 U가 나오면 map에 있는 초기 인구를 바꿔주고, 바뀐 정보를 다시 set에 넣어준다.

그리고 L이 나오면 set에서 가장 앞에 있는 것부터 탐색을 한다(set은 자동으로 정렬해줌)

탐색을 하는데 만약 map에 저장되어 있는 x번 경로의 값이 현재 set에 저장된 값과 다르다면 

연산을 통해 바뀐 것이기에 set에서 제거해주고 다음 경로를 확인한다.

#include <iostream>
#include <map>
#include <set>
#include <vector>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n, m; cin >> n >> m;
    set<pair<int, int>> nset, mset;
    map<int, int> nmp, mmp;

    for (int i = 1; i <= n; i++) {
        int k; cin >> k;
        nmp[i] = k;
        nset.insert({ k, i });
    }
    for (int i = 1; i <= m; i++) {
        int k; cin >> k;
        mmp[i + n] = k;
        mset.insert({ k, i + n });
    }

    int k; cin >> k;
    vector<pair<int, int>> removes;
    for (int i = 0; i < k; i++) {
        char c; cin >> c;
        if (c == 'U') {
            int x, y; cin >> x >> y;
            if (x > n) {
                mmp[x] = y;
                mset.insert({ y, x });
            }
            else {
                nmp[x] = y;
                nset.insert({ y, x });
            }
        }
        else {
            for (auto n : nset) {
                if (nmp[n.second] != n.first) {
                    removes.push_back(n);
                }
                else {
                    cout << n.second << " ";
                    break;
                }
            }
            for (pair<int, int> p : removes) nset.erase(p);
            removes.clear();
            for (auto n : mset) {
                if (mmp[n.second] != n.first) {
                    removes.push_back(n);
                }
                else {
                    cout << n.second << "\n";
                    break;
                }
            }
            for (pair<int, int> p : removes) mset.erase(p);
        }
    }
}

 

E번은 문제 이해를 못 하겠고, H번은 풀이가 아직 생각이 안 난다(생각나면 반례가 바로 떠오르고.. 이거 반복중..)

 

그래도 이제 에토리얼 없이도 잘 푸는 것 같다.ㅎ.ㅎ.ㅎ.ㅎ.