Codeforces Round #783 (Div. 2) 1466 → 1462

https://codeforces.com/contest/1665

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

 

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

 

A. Direction Change

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

Problem - A - Codeforces

문제

n*m그리드가 있다. 1,1에서 n,m으로 가려하는데 인접한 4방향으로 이동할 수 있지만 연속된 방향으로 2번 연속 이동을 하지 못한다. 이때 최소 이동비용을 출력하는 문제

 

풀이

 

1,1 -> n,n 으로 가는 비용을 계산해준 후 최종적으로 나오는 형태 ( x,0 또는 0,y)를 가는 최소비용을 계산해준다.

 

 

코드

 

    #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 x, y;
            cin >> x >> y;
            if (x == 1 && y == 1) {
                cout << 0 << '\n';
                continue;
            }
            if (x == 1) {
                if (y > 2)cout << -1;
                else cout << 1;
                cout << '\n';
                continue;
            }
            if (y == 1) {
                if (x > 2)cout << -1;
                else cout << 1;
                cout << '\n';
                continue;
            }
            long long ans = 0;
            long long MIN = min(x, y);
            ans += MIN - 1;
            ans += MIN - 1;
            if (x == y) {
                cout << ans << '\n';
                continue;
            }
            x -= MIN;
            y -= MIN;
            long long MAX = max(x, y);
            ans += (MAX) * 2LL-1LL;
            if (MAX % 2==0) {
                ans++;
            }
            cout << ans << '\n';
        }
    }

 

B. Social Distance

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

Problem - B - Codeforces

 

문제

 

n명의 사람과 m개의 의자가 있다. n명의 사람은 각 a[i]만큼 양옆에 빈자리가 있길 원한다. m개의 의자에 모든 사람을 각자 원하는대로 앉힐 수 있으면 YES를 아니라면 NO를 출력하는 문제

 

풀이

 

내림차순 sorting을 하면 그리디적으로 서로 빈 공간을 최대로 활용할 수 있다. 이렇게 앉힌다고 가정하고 의자의 개수를 세주면 된다.

 

코드

 

    #include <bits/stdc++.h>
    using namespace std;
    long long a[100001];
    int main() {
        ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
     
        int T;
        cin >> T;
        while (T--) {
            int n, m;
            cin >> n >> m;
            long long sum = 0;
            for (int i = 0; i < n; i++) {
                cin >> a[i];
            }
            if (n >= m) {
                cout << "NO\n";
                continue;
            }
            sort(a, a + n, greater<int>());
            for (int i = 0; i < n; i++) {
                sum++;
                if (i == (n - 1))break;
                sum += a[i];
            }
            sum += a[0];
            if (sum <= m)cout << "YES\n";
            else cout << "NO\n";
        }
    }

C. Make it Increasing

https://codeforces.com/contest/1668/problem/C

Problem - C - Codeforces

문제

 

길이가 n인 배열 a,b가 있다. b는 처음에 모두 0이고 a는 입력으로 주어진다. 한번의 operation에 b[i] += a[i] 또는 b[i]-=a[i]를 할 수 있고 b 배열을 오름차순으로 만들 기 위한 최소 operation을 출력하는 문제

 

풀이

 

각 위치에서 무조건 0번 operation하는 자리가 있다. 그 자리를 찾아 n^2으로 계산해주면 된다.

 

코드

    #include <bits/stdc++.h>
    using namespace std;
    long long a[5001];
    int main() {
        ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
        int n;
        cin >> n;
        for (int i = 0; i < n; i++)cin >> a[i];
        long long ans = INT64_MAX;
        for (int i = 0; i < n; i++) {
            int l = i - 1, r = i + 1;
            long long start = 0,sum=0;
            while (l >= 0) {
                long long div = start / a[l];
                div++;
                sum += div;
                start = a[l] * div;
                l--;
            }
            start = 0;
            while (r < n) {
                long long div = start / a[r];
                div++;
                sum += div;
                start = a[r] * div;
                r++;
            }
            ans = min(ans, sum);
        }
        cout << ans << '\n';
    }

 

 

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

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