Codeforces Round #771 (Div. 2) 1589 -> 1646

https://codeforces.com/contest/1638

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

 

!!!! 모든 답은 제 풀이일 뿐 정해가 아닐 수 있습니다 !!!!

 

A. Reverse

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

Problem - A - Codeforces

문제

 

n길이의 permutation을 입력받아 l,r 을 고른 후 l ~ r 인덱스 사이의 부분 수열을 뒤집는 연산을 할 한번만 할 때 사전적으로 가장 작은 permutation을 출력하는 문제

 

풀이

 

1부터 n까지 각 i위치에 숫자 i가 아닌 (가장 작은) 수를 찾아 i자리에 맞게 reverse 해주면 된다.

 

 

코드

 

    #include <bits/stdc++.h>
    using namespace std;
    int a[501];
    int main() {
        ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
        int T;
        cin >> T;
        while (T--) {
            int n;
            cin >> n;
            for (int i = 1; i <= n; i++) {
                cin >> a[i];
            }
            int l = -1, r = -1;
            for (int i = 1; i <= n; i++) {
                if (a[i] != i) {
                    l = i;
                    break;
                }
            }
            if (l == -1) {
                for (int i = 1; i <= n; i++)cout << a[i] << ' ';
                cout << '\n';
                continue;
            }
            for (int i = 1; i <= n; i++) {
                if (a[i] == l) {
                    r = i;
                    break;
                }
            }
            while (l < r) {
                swap(a[l], a[r]);
                l++; r--;
            }
            for (int i = 1; i <= n; i++)cout << a[i] << ' ';
            cout << '\n';
        }
    }

 

 

B. Odd Swap Sort

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

Problem - B - Codeforces

문제

 

n길이의 배열 a가 있다. 인덱스 i를 골라 a[i]+a[i+1] 이 홀수라면 swap할 수 있는 연산을 원하는 만큼 할 수 있을 때 전체적으로 a 배열을 오름차순으로 정렬할 수 있는지 출력하는 문제

 

풀이

 

짝수와 짝수를 합치면 짝수, 홀수와 홀수를 합치면 짝수이기 때문에 짝수는 짝수끼리 정렬이 되있는지 확인하고 홀수는 홀수끼리 정렬되있는지 확인한 후 되있으면 YES를 아니라면 NO를 출력한다.

 

코드

 

    #include <bits/stdc++.h>
    using namespace std;
    long long a[100001];
    vector<int> even,odd;
    int main() {
        ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
        int T;
        cin >> T;
        while (T--) {
            even.clear();
            odd.clear();
            int n;
            cin >> n;
            for (int i = 1; i <= n; i++) {
                cin >> a[i];
                if (a[i] % 2 == 0) {
                    even.push_back(a[i]);
                }
                else odd.push_back(a[i]);
            }
            bool flag = true;
            for (int i = 1; i < even.size(); i++) {
                if (even[i - 1] > even[i]) {
                    flag = false;
                    break;
                }
            }
            for (int i = 1; i < odd.size(); i++) {
                if (odd[i - 1] > odd[i]) {
                    flag = false;
                    break;
                }
            }
            if (flag)cout << "YES\n";
            else cout << "NO\n";
        }
    }

C. Inversion Graph

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

Problem - C - Codeforces

문제

 

n길이의 permutation과 무방향 그래프가 있다. permutation의 각 인덱스가 정점이고 , i < j 이고 p[i] > p[j]라면 둘의 정점을 edge로 연결한다. 이때 연결요소의 개수를 구하는 문제

 

풀이

 

인덱스 1부터 a[i]의 MAX값을 찾아 저장하면서 MAX<i라면 그래프는 새로 형성되는 원리를 이용해 계산하여 답을 출력해준다.

 

코드

 

    #include <bits/stdc++.h>
    using namespace std;
     
    int a[100001];
    int main() {
        ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
        int T;
        cin >> T;
        while (T--) {
            int n;
            cin >> n;
            for (int i = 1; i <= n; i++) {
                cin >> a[i];
            }
            int ans = 0;
            int r=0;
            for (int i = 1; i <= n; i++) {
                if (r < i) {
                    ans++;
                }
                r = max(r, a[i]);
            }
            cout << ans << '\n';
        }
    }

 

 

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

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