Codeforces Round #509 (Div. 2) 후기

처음으로 코드포스의 시스템을 경험해보았다.

일단 해커랭크처럼 영어로 되어 있기 때문에 해석하는 데에 약간의 시간이 걸리는 것은 어쩔 수 없는 모양.. ㅠㅠ

첫 도전의 결과는 너무 참담했다.. 겨우 2문제

B번 문제도 50분만에 겨우 풀었는데 예외 조건을 제대로 생각하지 못해서 시간을 너무 많이 썼다.

예외 찾는데만 문제 풀이 시간만큼을 더 써버렸으니..

A. Heist

사실 너무 쉬운 문제인데 문제 이해 + 해석 덕분에 약간 시간을 잡아 먹은듯 하다.

주어진 숫자를 오름차순으로 정렬한 다음 중간 중간 비어있는 숫자 간격이 몇인지 누적해서 체크하면 쉽게 구할 수 있다.

// Codeforces Round #509 (Div. 2)
// A. Heist
#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    freopen("../input.txt", "r", stdin);
 
    int num, result = 0;
    cin >> num;
    vector<int> arr(num);
    for (int i = 0; i < num; i++)
        cin >> arr[i];
    sort(arr.begin(), arr.end());
    for (int i = 1; i < num; i++)
        result += arr[i] - arr[i - 1] - 1;
    cout << result;
 
    return 0;
}

B. Buying a TV set

주어진 TV ratio를 일단 기약분수 꼴로 만드는 것이 핵심이다.

그리고 그 기약분수 형태가 주어진 범위 안에 속하는 모든 ratio를 구하면 풀 수 있다.

ul gcd(ul a, ul b) {
    ul c;
    while (b != 0) {
        c = a % b;
        a = b;
        b = c;
    }
    return a;
}

여기서 한가지 팁은 그 gcd로 나눈 몫을 그대로 활용하는 것이다.

ul num = gcd(x, y);
ul a = x / num, b = y / num;
ul result = num;

만약 이 숫자를 사용하지 않고 오로지 gcd의 배수 만으로 값을 구하려 한다면 시간초과가 난다.

while(x > w || y > h){
    result--;
    x -= a;
    y -= b;
}

그리고 x와 y가 입력 범위의 숫자보다 작거나 같은 조건을 만족해야 하기 때문에 gcd 만큼 빼주면서 범위를 한정시켜야한다.

// Codeforces Round #509 (Div. 2)
// B. Buying a TV set
#include <iostream>
 
using namespace std;
typedef unsigned long long ul;
 
ul gcd(ul a, ul b) {
    ul c;
    while (b != 0) {
        c = a % b;
        a = b;
        b = c;
    }
    return a;
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    freopen("../input.txt", "r", stdin);
    ul w, h, x, y;
    cin >> w >> h >> x >> y;
    ul num = gcd(x, y);
    ul a = x / num, b = y / num;
    ul result = num;
    while(x > w || y > h){
        result--;
        x -= a;
        y -= b;
    }
    while (true) {
        x += a;
        y += b;
        if(x <= w && y <= h)
            result++;
        else
            break;
    }
    cout << result;
 
    return 0;
}