COFO::1374D Zero Remainder Array

• Link : COFO::1374D
• 깔끔하게 풀었지만, 아직 1400점대는 시간이 좀 오래걸립니다.
• 아이디어가 떠오르기까지 걸리는 시간이 줄어들어야 빠르게 풀 수 있을 것 같습니다.

Problem

• level : 1400
• tag : math, sortings, two pointers

Point

• n, k가 주어집니다.
• 길이 n인 array a가 주어집니다.
• 최초 x=0으로 시작합니다.
• 2가지의 작업이 있습니다.
  • 하나는, a[i] = a[i] + x, x += 1
  • 다른 하나는, x += 1
• 작업의 갯수를 최소한으로 사용해서 a의 모든 원소가 k로 나눠지게 하고 싶습니다.
• 이때의 작업의 갯수를 출력합니다.

Design

• 이 문제의 난이도를 조절하는 부분은 같은 숫자가 여러 개 있을 수 있다는 점입니다.
• 숫자가 최대 한번씩만 등장하면, 오름차순으로 정렬하면 가장 큰 수의 값이 정답이 되겠지요
• 해당 문제는 기하적으로 그림을 그려서 생각하면 훨씬 수월합니다.
• testcase 2번째를 다음과 같이 표현할 수 있습니다.
  • 먼저 k가 넘는 값은 필요없으므로 모든 원소를 k의 나머지로만 취합니다.
  • 그리고, 모든 원소를 k-원소값 으로 치환합니다.
    • 이만큼만 더해주면 된다는 의미입니다.
  • 이제 이 값들을 2차원 평면에 그려봅니다.
    • x축은 더해줘야 하는 값, y축은 카운트입니다.
• 3 o o o x x
• 2 o o x x x
• 1 x x x x x

• 0 1 2 3 4 5 6

• 위와 같이 표현하고 x가 지나가는 선분을 그려보면 풀이를 떠올릴 수 있습니다.
  • o가 비어있는 부분이고 x가 들어차있는 부분입니다.
• 정답은 다음과 같습니다.
• 가장 갯수가 많은 숫자이면서 가장 큰 수가 기준이 됩니다.
  • 이때의 수를 num, 갯수를 cnt라고 할때
  • 답은 (cnt-1) * k + num + 1이 됩니다.
• 두 작업 모두 x를 무조건 1씩 증가시키므로, 증가시키는 길에 있는 모든 점(x)들은 알아서 자동으로 지워질 수 있습니다.
• 그렇다면 총 0부터 6까지 몇바퀴를 돌아야 하는지 선분으로 계속 이어보면, 5까지 2바퀴를 꼬박 돌고, 5까지 더해줘야한다는 점을 알 수 있습니다.

Big O(time)

• O(nlogn)

Code

#define rep(i, a, b) for(int i = (a); i<(b); i++)
#define r_rep(i, a, b) for(int i=(a); i>(b); i--)
#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
typedef long long ll;
using namespace std;

ll n, k;
map<ll, int> mp;
void input(){
    cin >> n >> k;
    mp.clear();
    rep(i, 0, n){
        ll x; cin >> x;
        if(x % k == 0) continue;
        mp[k - x%k]++;
    }
}

ll solve(){
    input();
    if(mp.size() == 0) return 0;
    ll cnt = 0, num = 0;
    for(auto it = mp.begin(); it != mp.end(); it++){
        if((it->second > cnt) || (it->second == cnt && it->first > num)){
            cnt = it->second;
            num = it->first;
        }
    }
    return (cnt-1) * k + num + 1;
}
int main(){
    freopen("input.txt", "r", stdin);
    int tc; cin >> tc;
    while(tc--)
        cout << solve() << '\n';
    return 0;
}