Codeforces Round #792 (Div. 1 + Div. 2) 1540 → 1565

https://codeforces.com/contest/1679

Dashboard - Codeforces Round #791 (Div. 2) - Codeforces

!!!! 모든 답은 제 풀이일 뿐 공부를 위한 올바른 정해가 아닐 수 있습니다 !!!!

 

A. Digit Minimization

https://codeforces.com/contest/1684/problem/A

Problem - A - Codeforces

문제

 

n자리의 수가 주어진다. 임의의 두개의 인덱스를 골라 위치를 swap하고 맨 뒤에 char을 없애는 과정을 자리수가 1이 될 때까지 반복했을 때 가장 작은 1자리 수를 출력하는 문제

 

풀이

 

길이가 2라면 2번째 char을 출력하고 이외에는 가장 작은 char을 출력하면 된다.

 

코드

 

    #include <bits/stdc++.h>
    using namespace std;
    string s;
    int main() {
        ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
        int T;
        cin >> T;
        while (T--) {
            cin >> s;
            char MIN = '9';
            if (s.size() == 2) {
                cout << s[1] << '\n';
            }
            else {
                for (int i = 0; i < s.size(); i++)MIN = min(MIN, s[i]);
                cout << MIN << '\n';
            }
     
        }
    }

 

B. Z mod X = C

https://codeforces.com/contest/1684/problem/B

Problem - B - Codeforces

문제

 

x%y = a , y % z = b, z % x = c 이고 a < b < c 로  a,b,c가 주어질때 x,y,z를 출력하는 문제

 

풀이

 

c가 가장 커서 x 를 가장 크게 구한다. 우선 y = b , z = c 로 잡고 x = b*( 무수히 큰 수) + a 를 하면 조건에 만족하게 구해진다.

 

 

코드

 

    #include <bits/stdc++.h>
    using namespace std;
     
    int main() {
        ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
        int T;
        cin >> T;
        while (T--) {
            long long a, b, c;
            cin >> a >> b >> c;
            long long y = b;
            long long x = y * 1000000000LL + a;
            long long z = c;
            cout << x << ' ' << y << ' ' << z << '\n';
            //cout << x % y << ' ' << y % z << ' ' << z % x << '\n';
        }
    }

D. Traps

https://codeforces.com/contest/1684/problem/D

Problem - D - Codeforces

문제

 

n개의 함정과 k 가 주어진다. i번째 함정을 밟으면 a[i] 만큼의 데미지를 입거나 최대 k번 점프할 수 있다. 점프하면은 a[i]번째를 건너뛰는 대신 이후의 값들이 1씩 증가한다. 이때 최소 데미지를 출력하는 문제.

 

풀이

 

증명은 못했지만 a[i] - (n-i) 로 우선순위를 매겨서 가장 큰 순서대로 k개를 빼면 값은 최대가 된다.

 

 

코드

    #include <bits/stdc++.h>
    using namespace std;
    long long a[200001];
    struct A {
        long long idx, val;
        bool operator<(const A& p)const {
            return val < p.val;
        }
    };
    priority_queue<A> pq;
    int main() {
        ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
        int T;
        cin >> T;
        while (T--) {
            while (!pq.empty())pq.pop();
            long long n, k;
            cin >> n >> k;
            for (int i = 1; i <= n; i++) {
                cin >> a[i];
            }
            long long cnt = 1;
            for (int i = n; i >= 0; i--) {
                pq.push({ i,a[i] - cnt });
                cnt++;
            }
            while (k--) {
                a[pq.top().idx] = 0;
                pq.pop();
            }
            long long ans = 0;
            cnt = 0;
            for (int i = 1; i <= n; i++) {
                if (a[i] == 0)cnt++;
                else {
                    ans += (a[i] + cnt);
                }
            }
            cout << ans << '\n';
        }
    }

 

 

자세한 설명에 중점을 두기보다는 대회 기록에 중점을 둔 글입니다 !

틀린 부분은 감사히 지적받겠습니다.