코드포스 Educational Codeforces Round 127 풀이 (A ~ C)

코드포스의 모든 Contest에는 에디토리얼이 따로 존재하지만 제가 공부하기 위해서 문제를 풀어보거나 에디토리얼을 번역하면서 이해하고, 그 내용을 정리해서 올립니다.

 

 

1671A. String Building

주어진 문자열을 aa, aaa, bb, bbb만으로 조합하여 만들 수 있는지의 여부를 구하는 문제입니다.

동일한 문자가 2개 이상 반복되는 경우 2와 3의 조합으로 언제나 만들 수 있기 때문에, 조합이 불가능한 경우는 하나의 "독립된" 문자가 존재하는 경우뿐입니다. (ex : aaaaa"b"aaaa)

 

따라서 고립된 하나의 단일 문자가 존재하는지를 검사하여 그러한 문자가 없다면 YES, 아니면 NO를 출력해주면 됩니다.

 

 

#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--) {
        string str; cin >> str;

        bool check = true;
        for(int i=0; i<str.length(); i++) {
            if(i == 0 && i == str.length()-1) check = false;
            else if(i == 0 && str[i+1] != str[i]) check = false;
            else if(i == str.length()-1 && str[i-1] != str[i]) check = false;
            else if(str[i-1] != str[i] && str[i+1] != str[i]) check = false;
        }

        if(check) cout << "YES\n";
        else cout << "NO\n";
    }
}

 

 

1671B. Consecutive Points Segment

주어진 N개의 x축 위의 점들에 대해, 각 점들에 대해 좌표를 +1 또는 -1만큼 움직이는 연산을 최대 1번 이하로 할 수 있다고 할 때, 모든 점을 연속된 정수로 만들 수 있는지의 여부를 구하는 문제입니다.

 

예를 들어 좌표가 1, 2, 4, 6, 7과 같이 주어졌다면 1, 2를 각각 오른쪽으로 1씩 옮기고 6, 7을 각각 왼쪽으로 1씩 옮겨서 2, 3, 4, 5, 6으로 연속된 정수의 배열로 만들 수 있습니다.

위와 같은 경우처럼 중간에 갭이 존재하는 경우 왼쪽의 그룹을 1씩 오른쪽으로 옮기고, 오른쪽의 그룹을 1씩 왼쪽으로 옮기는 것이 최선입니다. (즉, 이 이상 갭이 존재할 경우 연속된 정수로 만들 수 없다는 뜻)

 

따라서 중간에 비는 정수가 2개 이하라면 YES, 3개 이상이라면 NO를 출력해주면 됩니다.

 

 

#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--) {
        int N; cin >> N;

        vector<int> arr(N);
        for(int i=0; i<N; i++) cin >> arr[i];

        int gap = 0;
        for(int i=0; i<N-1; i++) gap += arr[i+1] - (arr[i] + 1);

        if(gap <= 2) cout << "YES\n";
        else cout << "NO\n";
    }
}

 

 

1671C. Dolce Vita

매일 x만큼의 금액으로 살 수 있는 최대한 많은 설탕을 산다고 하며 각 물품의 가격 a_i는 하루에 1씩 가격이 오를 때 몇 개의 물품을 살 수 있는지 구하는 문제입니다.

 

우선 가격 a_i들을 오름차순으로 정렬해주고 원소의 뒤에서부터 앞으로 넘어오면서 (해당 번호까지의 설탕을 살 수 있는 날짜 × 살 수 있는 설탕의 수)를 계산합니다.

그 다음부터는 해당 번호의 설탕을 살 수 없으므로 현재 가격의 총합 sum에서 a_i만큼을 빼주고 prev = curr로 값을 옮겨줍니다.

위의 과정을 반복하며 맨 앞 설탕까지 검사해주면 총 구매할 수 있는 설탕의 개수를 구해줄 수 있습니다.

 

 

#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 N, x; cin >> N >> x;

        vector<int> arr(N);
        long long sum = 0;
        for(int i=0; i<N; i++) {
            cin >> arr[i];
            sum += arr[i];
        }

        sort(arr.begin(), arr.end());

        long long ans = 0, curr, prev = -1;
        for(long long i=N-1; i>=0; i--) {
            if(x >= sum) curr = (x - sum) / (i + 1);
            else curr = -1;

            ans += (i + 1) * (curr - prev);
            prev = curr;

            sum -= arr[i];
        }

        cout << ans << "\n";
    }
}