Codeforces Round #612 (Div. 2)

문제 링크 : http://codeforces.com/contest/1287

 

A. Angry Students

문제 요약

Angry Students와 Patient Students가 있을 때, 최대의 Angry Student를 만들기까지 걸리는 시간을 구하는 문제이다.

 

접근 방법

P가 A보다 앞에 있으면 앞의 P는 절대 A로 변하지 않으므로, 이것을 제외한 후 P 앞에 있는 A를 대상으로 A 뒤에 있는 P의 개수 중 최댓값을 구하였다.

 

시간복잡도

O(n)

#include <bits/stdc++.h>
 
using namespace std;
 
int solution(string& S) {
    int init = 0;
    for(int i = 0; i < S.length(); i++) {
        init = i+1;
        if(S[i] == 'A') break;
    }
    
    int max_p = 0, count_p = 0;
    for(int i = init; i < S.length(); i++) {
        if(S[i] == 'P') {
            count_p++;
            max_p = max(max_p, count_p);
        } else {
            count_p = 0;
        }
    }
    
    return max_p;
}
 
int main(void) {
    int test_cases;
    cin >> test_cases;
    for(int i = 0; i < test_cases; i++) {
        int n;
        cin >> n;
        string s;
        s.reserve(n);
        cin >> s;
        cout << solution(s) << endl;
    }
    
    return 0;
}

 

B. Hyperset

문제 요약

여러 개의 카드 중 3개의 카드를 뽑는다. 이 3개의 카드는 세부 특성(모양, 색상 등)이 3개 모두 다르거나 3개 모두 같아지는 set의 개수를 구하는 문제이다.

 

접근 방법

우선 두 카드를 고른 후, 다른 하나의 카드가 set이 되려면 필요한 조건을 생성하고 이 조건을 map에 key로 넣는다. 이 작업을 반복하면 map에는 필요한 카드들의 목록이 생길 것이고, 맨 처음에 입력받은 카드의 리스트에 있는 것만 뽑아 개수를 세면 된다.

 

시간복잡도

STL map의 시간복잡도를 O(n)이라고 놓고 구하면 O(n^3)이 되므로 n이 최대 1500개일 때 3초 동안 수행이 가능하다.

#include <bits/stdc++.h>
 
using namespace std;
 
string str(string& A, string& B) {
    string ret = "";
    for(int i = 0; i < A.length(); i++) {
        if(A[i] == B[i]) {
            ret += A[i];
        } else {
            ret += ('S' + 'E' + 'T' - (A[i] + B[i]));
        }
    }
    return ret;
}
 
int solution(vector<string>& V) {
    map<string, int> m;
    for(int i = 0; i < V.size(); i++) {
        for(int j = i+1; j < V.size(); j++) {
            string s = str(V[i], V[j]);
            if(!m.count(s)) {
                m[s] = 1;
            } else {
                m[s]++;
            }
        }
    }
    int ret = 0;
    for(int i = 0; i < V.size(); i++) {
        ret += m[V[i]];
    }
    return ret / 3;
}
 
int main(void) {
    int n, k;
    cin >> n >> k;
    vector<string> V(n);
    for(int _n = 0; _n < n; _n++) {
        cin >> V[_n];
    }
    cout << solution(V) << endl;
    
    return 0;
}

 

총평

다른 사람이 푼 문제를 보면 상단에 #include <bits/stdc++.h>가 있는 것을 몇 번 보았는데, C++에서 사용되는 모든 헤더들을 include 시킨 것이라고 하여 이번엔 그렇게 풀어보았다.

C번 문제는 손으로는 풀 수 있었지만 코드로 작성하지 못하여 실패하였다. ㅠㅠ 너무 어려워..