Codeforces Round #601 (Div. 2)

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

 

A. Changing Volume 

문제 요약

임의의 음량 크기에서 자신이 원하는 음량 크기로 맞추는 데 필요한 최소 버튼 클릭 횟수를 구하는 문제이다.

 

접근 방법

무조건 큰 단위의 버튼을 누르는 게 유리하므로 -5 크기의 버튼을 음량의 차가 5 미만이 될 때까지 누르고, 5 미만이 되면 차에 따라 값을 구하면 될 것 같았다.

 

시간복잡도

O(1)

 

#include <iostream>
#include <algorithm>

using namespace std;

int solution(int A, int B) {
    if(A == B) return 0;
    if(A < B) swap(A, B); //A가 B보다 크도록
    
    int ret = (A - B) / 5; //무조건 -5를 누르는 게 이득
    int mod = (A - B) % 5; //0부터 4의 남은 음량 카운트
    ret += (mod + 1) / 2;
    
    return ret;
}

int main(void) {
    int T;
    cin >> T;
    
    for(int i = 0; i < T; i++) {
        int A, B;
        scanf("%d %d", &A, &B);
        printf("%d\n", solution(A, B));
    }
    
    return 0;
}

 

B. Fridge Lockers

문제 요약

다른 사람이 나의 냉장고를 열지 못하도록 하는 cost의 최솟값과 chain의 각 edge를 찾는 문제이다.

 

접근 방법

계속 그림을 그려보니까 예시처럼 그리지 않고 원처럼 그려도 된다. 또한 문제에서 주어진 제한으로는 m <= n인데, 생각해보면 n이 m보다 크면 모든 냉장고를 이을 수 없으므로 n = m밖에 되지 않는다. 

 

시간복잡도

Cost를 구하는 데 O(n)이 소요되었고 출력하는 데도 O(n)이 소요되었다.

 

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

using namespace std;

void solution(int N, int M, vector<int>& V) {
    if(N != M || N < 3) { //N = 2면 무조건 불가능, N이 M과 다르면 무조건 불가능
        printf("-1\n");
        return;
    }
    
    int S = 0; //Sum
    for(int i = 0; i < V.size(); i++) { //벡터의 모든 값 합하기
        S += V[i];
    }
    
    printf("%d\n", S * 2); //필요한 Cost는 Sum * 2
    for(int i = 1; i < N; i++) {
        printf("%d %d\n", i, i+1); //1 ~ N-1 까지 출력
    }
    printf("%d %d\n", 1, N); //1-N 출력
    
}

int main(void) {
    int T;
    cin >> T;
    
    for(int t = 0; t < T; t++) {
        int N, M;
        cin >> N >> M;
        vector<int> V;
        for(int n = 0; n < N; n++) {
            int temp;
            scanf("%d", &temp);
            V.push_back(temp);
        }
        solution(N, M, V);
    }
    
    return 0;
}

 

총평

C번 같은 경우엔 뭘 말하는 건지는 알겠는데, 이걸 도저히 식으로 옮길 수 없어서 풀지 못했다.

다른 문제는 손도 대지 못했고, 공식이 도출되는 A와 B번 같은 문제만 풀었다.

야근을 너무 많이 해서 공부할 시간이 평일 1시간과 주말밖에 없다. 이 시간을 잘 활용해야겠지.