[Codeforces] Round #704 (Div. 2)

A번(AC) - 정수론

문제자체는 쉽다. 3개의 숫자의 배수와 주어진 숫자 사이의 차이의 최솟값을 구하면 되는 문제이다.

 

몇가지 예시를 들면서 상황을 이해하면 쉽게 접근할 수 있는데 

예를 들어 3, 4, 5 3개의 숫자가 주어지고 10을 기준으로 차이의 최솟값을 구한다고 해보자

그러면 3 * 4과 10의 차이가 1, 4 * 3와 10 사이의 차이가 2, 5 * 2와 10 사이의 차이의 최솟값을 묻는 문제와 동치임을 쉽게 파악할 수 있다.

 

즉, 무조건 비교하는 숫자가 3개의 배수보다 적거나나 같을 수 밖에 없다는 사실을 파악할 수 있다.

이때, 결과적으로 p = 해당하는 수 * 몫 + 나머지로 분리해서 해당하는 수 - 나머지를 출력하는 것이 목표이다.

 

대략적으로 이 상황쯤 되어서 모듈러 연산을 추측했으면 충분하다.

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

using namespace std;
typedef long long ll;

int main(void){
    fastio;
    int t;
    cin >> t;

    for(int i = 0; i < t; i++){
        ll p, a, b, c;
        cin >> p >> a >> b >> c;
        cout << min(min((a - (p % a)) % a, (b - (p % b)) % b), (c - (p % c)) % c) << "\n";
    }
    return 0;
}

B번(WC) - 그리디

사실 다 풀었는데, 10^5가 10000인줄 알았다(^^)

 

최대가 되는 상황을 수학적으로 이해해보면 무조건 큰 숫자가 앞에 나오는 것이 유리하다.

 

왜냐하면, 제일 큰 숫자가 n과 같이 때문이다.

만약, a,b가 있고 l > m인 l, m을 잡았다고 하자

그러면 (1<= a, b <= n)인 a,b에 대해서 무조건 a * (n ^ l) >= b * (n ^ m)을 만족한다.

(등호는 b가 n일때만 성립한다.)

 

즉, 문제에서 input값의 특수성떄문에 그리디하게 가장 큰 숫자가 앞에 오게끔 설정해줄 때 가장 최적 구조를 만족하게 된다.

그리디 문제임을 파악하는 것이 핵심인 문제라고 할 수 있겠다.

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

using namespace std;

int main(void){
    fastio;
    int t;
    cin >> t;

    for(int i = 0; i < t; i++){
        int n;
        cin >> n;
        vector<int> data_store;
        int visited[100001] = {0};

        for(int i = 0; i < n; i++){
            int temp;
            cin >> temp;
            data_store.push_back(temp);
        }
        
        int max_value = n;
        vector<int> print_store;
        int index_end = n - 1;
        int index_check = n - 1;
        while(index_check >= 0){
            if(data_store[index_check] == max_value){
                visited[max_value] = 1;
                for(int i = index_check; i <= index_end; i++){
                    print_store.push_back(data_store[i]);
                }
                for(int i = max_value - 1; i >= 0; i--){
                    if(visited[i] == 0){
                        max_value = i;
                        break;
                    }
                }
                index_end = index_check - 1;
            }
            else{
                visited[data_store[index_check]] = 1;
            }
            index_check--;
        }

        for(int i = 0; i < n; i++){
            cout << print_store[i]  << " ";
        }
        cout << "\n";
    }
    return 0;
}

업데이트 예정

---------------------------------------

C번