Codeforces Round #600 (Div.2)

문제 링크 : https://codeforces.com/contest/1253

A. Single Push

문제 요약

길이가 같은 a, b 두 배열이 있는데, a[i]에서 a[j](i <= j)까지 k만큼을 더하면 b[i]에서 b[j]까지와 동일한 배열이 되는가를 확인하는 문제이다.

 

접근 방법

그냥.. 두 배열을 처음부터 탐색하다가 다른 부분이 나타나면 k를 정하고, 계속 k만큼의 차가 나는지 체크하고 [a[i], a[j]]가 아닌 부분에선 두 배열이 동일한지 체크하면 될 것이라 판단했다.

 

시간복잡도

두 배열을 동시에 한 번 순회하므로 O(n)이다.

#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

bool solution(vector<int>& A, vector<int>& B) {
    int size = A.size();
    bool l = false, r = false;
    int k = 0;
    
    for(int i = 0; i < size; i++) {
        if(A[i] != B[i]) {
            if(r) return false; //이미 l, r을 찾았을 경우 무조건 거짓
            if(l) { //l만 찾았으면 k를 체크
                if(A[i] + k != B[i]) return false; 
            }
            if(!l) { //l도 찾지 못했을 때
                k = B[i] - A[i];
                if(k < 1) return false; //k 양수 아니면 거짓
                l = true;
            }
        }
        if(l && !r && A[i] == B[i]) { //r 찾기
            r = true;
        }
    }
    return true;
}

int main(void) {
    int T;
    cin >> T;
    for(int t = 0; t < T; t++) {
        int L;
        cin >> L;
        vector<int> A;
        vector<int> B;
        for(int l = 0; l < L; l++) {
            int temp;
            scanf("%d", &temp);
            A.push_back(temp);
        }
        for(int l = 0; l < L; l++) {
            int temp;
            scanf("%d", &temp);
            B.push_back(temp);
        }
        cout << (solution(A, B) ? "YES" : "NO" ) << endl;
    }
    
    return 0;
}

 

B. Silly Mistake

문제 요약

출퇴근 시간 데이터를 잃어버린 회사에서 다른 데이터를 바탕으로 이 데이터를 복구하는 것에 관한 문제이다.

 

접근 방법

하루에 최대 한 번 출근할 수 있고 퇴근도 동일하므로, Set 자료구조를 사용하면 될 것이라 판단하였다.

 

시간복잡도

Set을 제외한다면 O(n)이려나..

#include <iostream>
#include <vector>
#include <set>

using namespace std;

bool solve(vector<int>& V, vector<int>& ret) {
    int sum = 0;
    set<int> s_day, s_history;
    
    if(V.size() % 2 == 1) return false;
    
    for(int i = 0; i < V.size(); i++) {
        int v = V[i];
        if(v > 0) {
            if(!s_history.insert(v).second || !s_day.insert(v).second) {
                return false;
            }
            s_history.insert(v);
        } else {
            if(s_day.erase(-v) != 1) {
                return false;
            }
            if(s_day.empty()) {
                ret.push_back(i+1);
                s_history.clear();
            }
        }
    }
    
    if(!s_day.empty() || ret.empty()) return false;
    
    return true;
}

int main(void) {
    int N;
    cin >> N;
    vector<int> V;
    int temp;
    for(int i = 0; i < N; i++) {
        cin >> temp;
        V.push_back(temp);
    }
    vector<int> ret;
    bool sol = solve(V, ret);
    if(!sol) {
        cout << "-1";
    } else {
        cout << ret.size() << endl;
        cout << ret[0];
        for(int i = 1; i < ret.size(); i++) {
            cout << " " << (ret[i] - ret[i-1]);
        }
    }
    cout << endl;
    return 0;
}

 

C. Sweets Eating

문제 요약

설탕이 많이 들어간 걸 빨리 먹어야 토탈 패널티가 줄어드므로(????) 매일마다의 제일 작은 패널티를 구하는 문제이다.

 

접근 방법

데이터가 많아 일반적 수식으로는 시간 내에 풀지 못할 것 같았고, 점화식을 세워서 DP로 문제를 해결하면 될 것 같았다.

 

시간복잡도

처음 정렬에 O(nlogn)이 소요되고 나머진 O(n)이 소요되므로 O(nlogn)이 소요된다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<long long> solve(int M, vector<int>& V) {
    vector<long long> ret;
    sort(V.begin(), V.end());

    vector<long long> S;
    long long sum = 0;
    
    for(int i = 0; i < V.size(); i++) { //Sum 미리 계산
        sum += V[i];
        S.push_back(sum);
    }
    
    vector<long long> D;
    
    for(int i = 0; i < M; i++) { //점화식 초기값 계산
        D.push_back(S[i]);
    }
    
    for(int i = M; i < V.size(); i++) { //DP
        D.push_back(S[i] + D[i - M]);
    }
    
    return D;
}

int main(void) {
    int N, M;
    cin >> N >> M;
    
    vector<int> V;
    
    for(int i = 0; i < N; i++) {
        int temp;
        scanf("%d", &temp);
        V.push_back(temp);
    }
    
    vector<long long> sol = solve(M, V);
    
    for(int i = 0; i < sol.size(); i++) {
        cout << sol[i] << " ";
    }
    
    return 0;
}

 

총평

이번엔 어찌 3문제까지 풀긴 했는데, 뒤의 그래프 문제부터는 손을 못 대겠다.

영어도 열심히 공부해야 문제 이해도 빠를텐데..