레벨 업( BOJ 25405 )

문제 : https://www.acmicpc.net/problem/25405

25405번: 레벨 업

 

문제 파악하기

N개의 캐릭터를 조건에 맞게 레벨업 시켰을 때의 결과를 출력하는 문제입니다. 캐릭터는 K개의 캐릭터를 동시에 1씩 레벨업 할 수 있으며, 총 M번 레벨업시킬 수 있습니다. N과 M의 범위에 따라 해결할 수 있는 방식과 난이도가 달라지는 문제로, 전체 문제를 해결하기 위해서는 레벨이 올라가는 특징을 적절하게 캐치해야 합니다.

 

문제 해결하기

그렇다면 문제를 해결하기 위해서는 어떤 특징을 눈여겨 보아야할까요? 눈치채기 가장 쉬운 방법은 M의 값을 바꿔가면서 관찰해보면 됩니다. 만약 캐릭터의 레벨이 { 2 4 6 8 }이고, M=1이라면 다음과 같은 과정으로 레벨이 증가하게 됩니다.

 

{ 2 4 6 8 } > { 3 4 6 8 } > {4 4 6 8} > {4 5 6 8} > { 5 5 6 8 } > { 5 6 6 8 } > ….

 

캐릭터의 레벨 현황을 잘 살펴보면 캐릭터들의 레벨이 비슷해지는 걸 확인할 수 있습니다. 그럼 이번에는 M=2일 때 어떤 과정으로 레벨이 증가하는지 살펴보겠습니다.

 

{ 2 4 6 8 } > { 3 5 6 8 } > { 4 6 6 8 } > { 5 6 7 8 } > ….

 

M=1과 M=2일 때의 상황을 살펴보면 우리는 2가지 정보를 얻을 수 있습니다. 첫 번째, 레벨을 올릴수록 모든 캐릭터들의 레벨은 비슷해집니다. 두 번째, 크기가 비슷해지는 숫자들은 K번째 캐릭터의 레벨과 비슷해집니다. 두 가지 정보를 종합해보면 모든 캐릭터들은 K번째 캐릭터의 레벨과 비슷해지면서 레벨이 증가한다는 결론을 도출할 수 있습니다.

결론을 살펴보면 K번째 캐릭터의 레벨이 문제를 해결하기 위한 핵심요소라고 할 수 있습니다. 그렇다면 K번째 캐릭터의 레벨을 기준으로 N개의 캐릭터를 3개의 그룹으로 나눌 수 있습니다. 여기서 K번째 캐릭터와 비슷한 캐릭터라는 건 K번째 캐릭터의 레벨을 inp[K]라고 정의할 때, { inp[K], inp[K]+1 }을 만족하는 캐릭터를 의미합니다.

 

{ K번째 캐릭터보다 레벨이 낮음(A), K번째 캐릭터와 레벨이 비슷함(B), K번째 캐릭터보다 레벨이 높음(C) }

그룹 A : K번째 캐릭터보다 레벨이 낮은 캐릭터들로, 이 그룹의 캐릭터들은 항상 레벨이 증가합니다.

그룹 B : K번째 캐릭터와 레벨이 비슷한 캐릭터들로, 이 그룹의 캐릭터들은 번갈아가며 레벨이 증가합니다.

그룹 C : K번째 캐릭터보다 레벨이 높은 캐릭터들로, 이 그룹의 캐릭터들은 레벨이 증가하지 않습니다.

 

그룹을 관찰해서 도출할 점은 그룹 A와 그룹 C의 캐릭터들은 그룹 B로 서서히 이동하게 된다는 점입니다. 레벨이 증가하는 속도가 { 그룹 A > 그룹 B > 그룹 C } 를 만족하기에 결국 충분한 레벨업 과정을 거치면 모든 캐릭터들은 그룹 B로 이동하여 K번째 캐릭터와 비슷한 레벨을 가지게 됩니다. 따라서, 우리는 모든 과정을 시뮬레이션할 필요 없이 각각의 캐릭터가 언제 그룹 B로 들어오는지 확인만 하면 레벨업이 마무리되었을 때의 상황을 구할 수 있습니다.

 

그렇다면 어떻게 해야 각각의 캐릭터가 그룹 B로 이동하는 시점을 알 수 있을까요? 여기서 우리는 그룹 B에 초점을 맞추면 됩니다. 그룹 B로 이동한다는 건 그룹 A 혹은 그룹 C의 경계에 위치한 캐릭터가 K번째 캐릭터와 레벨이 비슷해진다는 점입니다. 그리고 레벨은 레벨업 과정을 거칠수록 항상 증가합니다. 따라서, 우리는 이분 탐색을 통한 파라메트릭 서치를 활용할 수 있습니다. 각 그룹의 경계에 있는 캐릭터가 K번째 캐릭터의 값과 비슷해지기 위해 필요한 최소 레벨업 횟수를 구한 다음, 더 작은 횟수만큼 레벨업을 시켜 그룹 B로 캐릭터를 이동시키면 됩니다. 그리고 이 과정에서 그룹 B의 범위는 [ l, r ]로 설정한 다음, inp[l-1]과 inp[r+1]을 각각 비교하면서 범위를 서서히 늘리면서 처리할 수 있습니다. 다만, 주의할 점은 그룹 A와 그룹 C의 캐릭터가 언제 이동하는지를 시뮬레이션이 아닌 직접 계산해야 한다는 점입니다. 그룹 A와 그룹 C의 값은 계산하기 쉽습니다. 우리가 신경쓸 캐릭터는 그룹 B의 경계에 위치한 캐릭터입니다. 경계에 위치한 캐릭터를 각각 inp[ l ]과 inp[ r ]로 정의하겠습니다. inp[ l ]과 inp[ r ]의 레벨업 상태를 구하는 건 막막할 수 있지만, 사고를 살짝 바꾸면 어렵지 않게 구할 수 있습니다.

 

우선, 그룹 B의 값들을 각각의 숫자가 그룹 B의 크기(Bsz) 갯수만큼 나열된 수열 중 일부분이라고 상상해보겠습니다. 예를 들어 Bsz=3이고 현재 그룹 B = { 2 2 3 3 }이라면 다음과 같은 상황을 의미합니다.

 

1 1 1 1 2 2 { 2 2 3 3 } 3 3 4 4 4 4 5 5 ….

 

이 상태에서 만약 2개의 캐릭터가 3번 레벨업한다면 어떻게 될까요? 2개의 캐릭터가 레벨업을 한다는 건 그룹 B의 위치가 오른쪽으로 2칸 이동한다는 의미입니다. 그리고 이 과정을 총 3번 한다면 오른쪽으로 2*3 = 6칸 이동한다는 의미입니다.

 

1 1 1 1 2 2 2 2 3 3 3 3 { 4 4 4 4 } 5 5 ….

 

이렇게 그룹 B의 상태를 상상해서 얻을 수 있는 이점은 산술 연산자를 통해 간단하게 그룹 B의 상태를 구할 수 있다는 것입니다. 각각의 숫자에서의 위치를 idx로 설정해보겠습니다. 이전에 가정했던 그룹 B = { 2 2 3 3 }은 숫자 2의 관점에서 2번째 인덱스부터 시작하고 있기에 idx의 초깃값은 2가 됩니다. 이 상태에서 2개의 캐릭터(K)를 3번(m) 레벨업하는 과정을 수식으로 구하면 다음과 같습니다.

 

nxtL = inp[ l ] + (idx + Km)/Bsz = 2 + ( 2 + 23 )/4 = 2 + 2 = 4

nxtR = inp[ l ] + (idx + Km + (Bsz-1))/Bsz = 2 + ( 2 + 23 + 3 )/4 = 4

 

그룹 B의 값을 { nxtL ~ nxtR } 이라고 하면 직접 수식으로 계산한 상태와 시뮬레이션한 상태가 동일하다는 걸 확인할 수 있습니다. 또한, idx의 값 역시 다음과 같은 수식으로 한번에 구할 수 있습니다.

 

idx = (idx + Km)%Bsz = ( 2 + 23 )%4 = 0

 

여기서 간과하지 말아야할 점은 idx의 값은 그룹 A의 캐릭터와 들어올 때와 그룹 C의 캐릭터가 들어올 때 살짝 달라진다는 점입니다. 그룹 A가 들어올 때에는 idx의 값은 변함없지만 그룹 C의 캐릭터가 들어오면 최댓값이 늘어나기에 기본적으로 idx의 값이 1씩 증가합니다. 단, idx = 0인 경우에는 증가하지 않기에 예외로 처리해야 합니다.

 

이렇게 수식을 사용하여 상태를 구하면 N개의 캐릭터에 대해 O(logN)번 계산하기에 전체 시간복잡도는 O(NlogN)이 되며, 이정도의 알고리즘이면 충분히 문제를 해결할 수 있습니다. 자세한 소스코드는 다음과 같습니다.

 

소스코드

#include <stdio.h>
#include <algorithm>
#define NMAX 100010
#define INF 0x7FFFFFFFFFFFFFFF
typedef long long int lint;
using namespace std;
 
int N, M, K;
lint inp[NMAX];
 
lint l, r, idx, Bsz;
lint a, b, valL, valR;
lint ll, rr, mid, cur;
 
int main() {
    // 입력
    scanf("%d", &N);
    for(int i=0;i<N;i++) scanf("%lld", &inp[i]);
    scanf("%d %d", &M, &K);
 
    sort(inp, inp+N);
 
    // 그룹 나누기 A / B / C
    // A는 {inp[K]보다 작은 숫자}, B에는 {inp[K] ~ (inp[K]+1)}, C에는 {inp[k]+1보다 큰 숫자}
    // k0은 inp[K]의 개수, k1은 inp[K]+1의 개수
    l = r = K-1;
    while(0<l or r<N-1) {
        Bsz = (r-l)+1;
 
        // 그룹 A에서 그룹 B로 넘어오기 위해 필요한 레벨업 횟수
        valL = INF;
        if(l > 0) {
            ll = 0; rr = M;
            while(ll<=rr) {
                mid = (ll+rr)/2;
 
                // 그룹 B의 값들을 슬라이딩 윈도우로 계산하기
                // 예를 들어 그룹 B에 { 2 2 3 3 3 } 값이 있으며, 3개씩 증가한다고 가정하면
                // 2 2 3 3 3 3 3 4 4 4 4 4 5 5 5 5 5 ... 수열에서 3칸씩 왼쪽으로 이동하기
                a = (inp[l-1]+cur) + mid;
                b = inp[l] + (idx + (K-l)*mid)/Bsz;
 
                if(a < b) ll = mid+1;
                else {
                    if(a == b) valL = min( valL, mid );
                    rr = mid-1;
                }
            }
        }
 
        // 그룹 C에서 그룹 B로 넘어오기 위해 필요한 레벨업 횟수
        valR = INF;
        if(r < N-1) {
            ll = 0; rr = M;
 
            while(ll<=rr) {
                mid = (ll+rr)/2;
 
                a = inp[l] + (idx + (K-l)*mid + (Bsz-1))/Bsz;
                b = inp[r+1];
 
                if(a < b) ll = mid+1;
                else {
                    if(a == b) valR = min( valR, mid );
                    rr = mid-1;
                }
            }
        }
 
        // 양쪽 모두 넘어올 수 없는 경우
        if(valL>M and valR>M) break;
        else {
            // 더 작은 값이 필요한 그룹의 값 추가하기
            if(valL < valR) {
                // 그룹 A에서 그룹 B로 가져오기
                inp[l-1] = inp[l-1] + cur + valL;
                inp[r] = inp[l-1] + (idx + Bsz)/Bsz;
 
                // sz개씩 나열된 수열에서의 위치 >> (inp[K]+1) 값의 개수
                idx = (idx + (K-l)*valL)%Bsz;
 
                cur += valL;
                M -= valL;
                l--;
            }
            else {
                // 그룹 C에서 그룹 B로 가져오기
                inp[l] = inp[l] + (idx + (K-l)*valR)/Bsz;
                inp[r+1] = inp[l] + (idx+Bsz)/Bsz;
 
                // 나열된 수열에서의 위치 >> 0인 경우를 제외하고 1씩 증가됨
                // Ex. ( 5 5 5 )에서 5가 추가되면 여전히 idx = 0 / ( 5 5 6 )에서 6이 추가되면 idx = 2로 증가함
                idx = (idx + (K-l)*valR)%Bsz;
                if(idx>0) idx++;
 
                cur += valR;
                M -= valR;
                r++;
            }
        }
 
    }
 
    // 남아있는 값 더하기
    if(M > 0) {
        Bsz = (r-l)+1;
 
        inp[l] = inp[l] + (idx + (K-l)*M)/Bsz;
        inp[r] = inp[l] + (idx + (Bsz-1))/Bsz;
 
        idx = (idx + (K-l)*M)%Bsz;
 
        cur += M;
        M = 0;
    }
 
    // 갱신값 반영
    for(int i=0;i<=r;i++) {
        if(i<l) inp[i] += cur;
        else if(i<=r-idx) inp[i] = inp[l];
        else inp[i] = inp[l]+1;
    }
 
    // 출력
    for(int i=0;i<N;i++) printf("%lld ", inp[i]);
}
 

후기

별다른 자료구조와 알고리즘을 사용하지 않지만 상당히 머리아팠던 문제입니다. 관찰과 아이디어가 필요한 문제로 정올 문제에 걸맞는 좋은 문제라고 생각합니다. 정올 및 PS 공부에 진심인 사람들에게 추천하는 문제입니다.