두 배( BOJ 31963 )

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

 

문제 파악하기

 

주어진 수열을 오름차순으로 만들기 위해 필요한 연산의 최소 횟수를 구하는 문제입니다. 사용할 수 있는 연산은 2배 하는 연산 1가지이며, 최대 250,000개의 숫자로 구성된 수열이 제시됩니다. 문제 자체는 이해하기 어렵지 않지만 은근 생각할 사항이 많은 문제입니다. 맨 왼쪽 부터 오른쪽 방향으로 숫자들을 하나씩 오름차순으로 맞추는 기본 베이스는 유추하기 쉽습니다. 다만, 여기서 어떻게 해야 시간 초과에 걸리지 않으면서 모든 숫자들을 바꿀 수 있을지는 생각을 필요로 합니다. 여기서 중요한 키워드는 기록하기 입니다.

 

문제 해결하기

이 문제를 효율적으로 해결하기 위해서는 사용할 수 있는 유일한 연산인 2배 연산에 초점을 맞출 수 있습니다. 수열을 오름차순으로 맞추기 위해서 꼭 직접 2배씩 곱할 필요는 없습니다. 만약 이전에 한 숫자를 계산한 기록이 있다면 그 기록을 참고해서 몇 번 더 곱할 지 계산하면 효율적으로 문제를 해결할 수 있습니다. 예를 들어, 현재 확인할 숫자 x는 이전 계산에서 10번의 2배 연산을 적용했다고 가정해보겠습니다. 그렇다면 우리는 x에 최소 10번 이상의 2배 연산을 적용해야 한다는 사실을 유추할 수 있습니다. 왜냐하면 현재 x보다 왼쪽에 있는 값이 10번 2배 연산을 적용했다면 현재 x값도 10번 이상 2배 연산을 해야 수열이 오름차순이 될 수 있기 때문입니다. 따라서, 우리는 모든 숫자에 대해 2배 연산을 적용한 횟수를 기록하는 배열 check를 사용할 예정입니다.

 

check[x] : 숫자 x에 2배 연산을 적용한 횟수

 

그럼 우리에게 남은 일은 check[x]와 숫자들을 활용해 크기를 비교하는 일 뿐입니다. 비교할 숫자는 현재 확인할 숫자의 바로 왼쪽 값이며 앞으로 확인할 숫자는 inp[i]로, 확인할 숫자와 크기를 비교할 숫자는 inp[i-1]로 표현하겠습니다. 우리는 inp[i]와 inp[i-1]의 크기를 비교하며 각각의 상황에 어떤 값을 확인해야 하는지 하나씩 확인해보겠습니다.

 

(1) inp[i-1] < inp[i] 인 경우

현재 숫자가 왼쪽보다 큰 경우는 우선 inp[i-1]가 inp[i]보다 커지기 위해 필요한 2배 연산 횟수인 diff 값이 필요합니다. 그리고 inp[i-1]을 이전에 연산한 횟수에서 diff을 빼주면 우리는 inp[i-1]가 inp[i]에게 영향을 미치는 횟수인 bef를 구할 수 있습니다. 여기서 영향을 미치는 횟수란 inp[i-1]이 inp[i]보다 큰 숫자이면서 2배 연산을 적용한 횟수입니다. 따라서, 우리는 inp[i]에 적용한 연산 횟수(check[inp[i]])가 항상 bef보다 커야 합니다. 만약 check[inp[i]]가 bef보다 작다면 inp[i-1]이 더 큰 숫자이기 때문에 bef보다 한번 더 연산을 적용해야하며, 이를 수식으로 표현하면 check[inp[i]] = bef+1 이 됩니다.

>> if(bef >= check[inp[i]]) check[inp[i]] = bef+1;

 

(2) inp[i-1] > inp[i] 인 경우

현재 숫자가 왼쪽보다 작은 경우는 inp[i]가 inp[i-1]보다 크거나 같기 위해 필요한 2배 연산 횟수인 diff 값을 구해야 합니다. 그리고 현재 inp[i]에 연산이 적용된 횟수에서 diff를 빼주면 inp[i-1]에 영향을 미치는 횟수인 cur를 구할 수 있습니다. 여기서 영향을 미치는 횟수란 inp[i]가 inp[i-1] 이상인 숫자이면서 2배 연산을 적용한 횟수입니다. 따라서, 우리는 cur의 횟수가 inp[i-1]의 횟수보다 작다면 연산 횟수가 부족하다고 할 수 있으며, 이 경우에는 inp[i-1]에 연산을 적용한 횟수에 diff 값을 더해준 횟수만큼 2배 연산을 적용해야 하며, 이를 수식으로 표현하면 check[inp[i]] = check[inp[i-1]] + bef 가 됩니다.

>> if(check[inp[i-1]] > cur) check[inp[i]] = check[inp[i-1]] + diff;

 

(3) inp[i-1] == inp[i] 인 경우

서로 같은 숫자인 경우에는 따로 연산이 필요 없습니다.

 

 

이렇게 구한 check[inp[i]]의 값을 전체 횟수 값에 누적해서 더하면 문제를 해결할 수 있습니다. 자세한 소스코드는 다음과 같습니다.

 

소스코드

#include <stdio.h>
 
int N;
int inp[250010];
 
long long diff, bef, cur;
long long ret;
 
long long check[1000010];
 
int getDiff(int a, int b, int f) {
    int ret = 0;
    
    while(a <= b) {
        if(f and a == b) break;
        
        a *= 2;
        ret++;
    }
    
    return ret;
}
 
int main() {
    scanf("%d", &N);
    for(int i=1;i<=N;i++) scanf("%d", &inp[i]);
    
    for(int i=2;i<=N;i++) {
        if(inp[i-1] < inp[i]) {
            diff = getDiff(inp[i-1], inp[i], 0);
            
            bef = check[inp[i-1]] - diff;
            if(bef >= check[inp[i]]) check[inp[i]] = bef+1;
            
        }
        else if(inp[i-1] > inp[i]) {
            diff = getDiff(inp[i], inp[i-1], 1);
            
            cur = check[inp[i]] - diff;
            if(check[inp[i-1]] > cur) check[inp[i]] = check[inp[i-1]] + diff;
        }
        
        ret += check[inp[i]];
        
    }
    
    printf("%lld", ret);
}
 

 

후기

알고리즘은 떠올리기 쉬웠지만 세부적인 구현은 살짝 까다로웠던 문제입니다. 정올 문제에 걸맞는 그리디 + 수학 유형의 문제였기에 올림피아드를 준비하는 학생들에게 추천하는 문제입니다.