Codeforces Round #610 (Div. 2)

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

 

A. Temporarily unavailable

문제 요약

어떤 범위 안의 직선에서 기지국이 커버를 할 수 없는 범위의 길이를 반환하는 문제이다.

 

접근 방법

직선의 양 끝 점을 a, b라고 하고, 기지국을 c라고 하면 3가지의 경우가 나온다. c-a-b, a-c-b, a-b-c의 경우가 되는데, 이에 맞추어서 공식을 유도하여 접근하면 된다.

 

시간복잡도

단순 공식 사용이므로 O(1)

#include <iostream>
#include <algorithm>

using namespace std;

int solution(int a, int b, int c, int r) {
    //c의 커버리지 r이 a-b 직선에 닿지 않으면 원하지 않는 값이 출력되므로 min 사용
    return min(b-a, max(0, c-r-a) + max(0, b-(c+r)));
}

int main(void) {
    int T;
    cin >> T;
    for(int i = 0; i < T; i++) {
        int a, b, c, r;
        scanf("%d %d %d %d", &a, &b, &c, &r);
        if(a > b) 
            printf("%d\n", solution(b, a, c, r));
        else
            printf("%d\n", solution(a, b, c, r));
    }
    return 0;
}

 

B. K for the Price of One

문제 요약

k개의 물건을 그 중 제일 비싼 한 물건의 가격으로 살 수 있는데, 얼마나 많은 물건을 구매할 수 있는지 확인하는 문제이다.

 

접근 방법

처음엔 문제 해석을 잘못하여 [1..k] 까지의 모든 정수만큼 k를 선택하여 구매할 수 있는 것인 줄 알고 매우 머리가 아팠는데, 다시 천천히 읽어보니 무조건 k개를 사든지, 1개를 사든지 선택하는 것이라 다시 생각을 해보았고, 손으로 문제를 풀어 보니 DP를 쓰는 게 제일 낫다는 결론을 내었다.

 

시간복잡도

sort에서 O(nlogn)을 잡아먹고, 아래 DP에서 O(n)씩 잡아먹으므로 O(nlogn)이다.

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

using namespace std;

int solution(vector<int>& a, int n, int p, int k) {
    sort(a.begin(), a.end());
    vector<int> cache(n+1); //[0...n]
    cache[0] = 0;
    for(int i = 1; i < k; i++) {
        cache[i] = cache[i-1] + a[i-1];
    }
    for(int i = k; i <= n; i++) {
        cache[i] = cache[i-k] + a[i-1];
    }
    int ret = 0;
    for(int i = 1; i <= n; i++) {
        if(cache[i] <= p) {
            ret = i;
        }
    }
    return ret;
    
}

int main(void) {
    int T;
    cin >> T;
    for(int i = 0; i < T; i++) {
        int n, p, k;
        scanf("%d %d %d", &n, &p, &k);
        vector<int> a(n);
        for(int j = 0; j < n; j++) {
            cin >> a[j];
        }
        cout << solution(a, n, p, k) << endl;
    }
    
    return 0;
}

 

총평

C번 문제를 풀기 위해 3일을 머리를 잡고 싸맸는데 결국 원하는 답이 나오지 않았다.

어제 드디어 Example input을 해결하고 submit을 했지만 test 2의 한 input에서 계속 틀렸다고 나왔다.

그래서 입력값을 확인하려고 했는데 Codeforces Input에서는 잘려서 확인이 불가능했다.

그래서 구글에 쳐보니(게시글), 오류가 나는 입력을 출력해보라고 하였다.

if(test_cases == 10000 && i == 38) {
	printf("%d--%d--%d--%d--", n, T, a, b);
	for(int j = 0; j < n; j++) printf("%d--", input[j].diff);
	for(int j = 0; j < n; j++) printf("%d--", input[j].t);
}

그래서 이렇게 출력해보았다.

Checker Log
wrong output format Expected integer, but "6--14--2--5--2--5--2--2--5--2--0--10--6--3--0--2--1" found

맨 마지막의 1은 solution의 return값인 1이다. (하지만 결국 풀지 못했다 ㅜㅠ)