Codeforces Round #789 (Div. 2) 1679 → 1598

https://codeforces.com/contest/1678

https://codeforces.com/contest/1678

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

 

A. Tokitsukaze and All Zero Sequence

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

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

문제

 

길이가 n인 배열 a가 주어진다. 각 operation마다 a[i]와 a[i]를 골라

1. a[i] = a[j] 라면 둘중 하나를 0으로 바꾼다.

2. 아니라면 두 값을 min(a[i],a[j])로 바꾼다.

모든 원소를 0으로 바꾸고자 할 때 최소 연산의 수를 출력하는 문제

 

풀이

 

원소중 하나라도 0으로 채워져있다면 답은 n- (0의 개수), 그게 아니라면 a[i] = a[j]인 원소가 하나라도 있다면 답은 n, 아니라면 답은 n+1을 출력해주면 된다.

 

 

코드

 

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

 

B1. Tokitsukaze and Good 01-String (easy version)

https://codeforces.com/contest/1678/problem/B1

https://codeforces.com/contest/1678/problem/B1

문제

 

짝수 길이의 n인 binary string이 주어진다. 연속된 짝수 길이의 같은 문자의 substring으로 나누고자 한다. 원하는 원소를 골라 바꿀 수 있을 때 나누는게 가능한 최소 operation을 출력하는 문제

 

풀이

 

짝수 길이라면 가장 앞에서부터 2개씩 끊는게 이득이니 a[i] != a[i+1] (단 i는 짝수 인덱스) 의 개수를 출력해주면 된다.

 

 

코드

 

    #include <bits/stdc++.h> 
    using namespace std;
    struct A {
        int l, r, cnt;
     
    };
    string s;
    vector<A> v;
    int main() {
        ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
     
     
        int T;
        cin >> T;
        while (T--){
            v.clear();
            int n;
            cin >> n;
            cin >> s;
            for (int i = 0; i < n; i++) {
                int cnt = 1, i2 = i + 1;
                while (i2 < n) {
                    if (s[i] == s[i2])cnt++;
                    else break;
                    i2++;
                }
                i = i2 - 1;
                v.push_back({i,i2,cnt});
            }
            bool flag = true;
            for (int i = 0; i < v.size(); i++) {
                if (v[i].cnt % 2) {
                    flag = false;
                    break;
                }
            }
            if (flag)cout << "0\n";
            else {
                int ans = 0;
                for (int i = 0; i < n; i+=2) {
                    if (s[i] != s[i + 1])ans++;
                }
                cout << ans << '\n';
            }
            
     
        }
     
    }

 

 

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

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