Simple Operations on Sequence( Atcoder 232-F )

문제 : https://atcoder.jp/contests/abc232/tasks/abc232_f

F - Simple Operations on Sequence

 

문제 파악하기

N개의 숫자로 이루어진 A 수열의 값을 변경하여 B 수열과 동일하게 만드는데 필요한 최소 비용을 구하는 문제입니다. 우리는 다음 2가지 작업을 통해 A 수열의 값을 바꿀 수 있습니다.

(1) X만큼의 비용을 들어 A_i의 값 1 증가/감소 시키기

(2) Y만큼의 비용을 들어 A_i의 값과 A_i+1의 값 교환하기

 

위의 2가지 작업으로 어떻게 수열 A와 B를 동일하게 만들까요? 우선 문제를 쉽게 바꿔봅시다. 동일하게 만든다는 건 결국 모든 B의 값은 A의 값과 같아진다는 의미입니다. 그렇다면 우리는 수열 B의 관점에서 문제를 바라봅시다.

 

문제 해결하기

수열 B의 관점에서 문제를 바라보면 조금은 간단해집니다. 수열 A의 값 중 하나를 선택해서 B_i와 같아지게 만들면 됩니다. 즉, 수열 A의 값 중 하나의 값과 B_i를 매칭시키면 됩니다. 선택된 매칭값 A_i는 Y만큼의 비용을 소모하여 B_i와 동일한 위치로 이동한 다음, X만큼의 비용을 소모하여 B_i의 값으로 바꾸면 됩니다. 물론 이동할 때와 값을 변경할 때에는 적절한 횟수만큼 반복해야 합니다. 이렇게 수열 B의 첫번째 값부터 마지막 값까지 모두 수열 A의 값과 매칭시키면 지금까지 사용한 비용이 나오며, 여기서 최솟값을 구하면 됩니다.

 

모든 값을 탐색하기에 적절한 함수를 설계해봅시다. 함수를 설계할 때에는 현재 상태를 표현할 수 있는 매개변수를 선택해야 합니다. 이 문제를 해결하기 위해 적절한 매개변수는 2개입니다. 첫 번째, 현재 B_i의 인덱스 값(idxB)입니다. 현재 B에서 매칭시키고 있는 B_i의 인덱스 값을 알고 있어야 추가로 드는 비용을 알 수 있습니다. 두 번째, 현재 A_i의 사용여부(check)입니다. 수열 A의 모든 숫자의 사용 여부를 알고 있어야 합니다. 그래야 나중에 Bi를 매칭시킬 때, 중복으로 매칭시키지 않기 때문입니다. 우리는 이 2가지 매개변수를 통해 다음 상태를 구할 수 있으며, 결국에는 우리가 원하는 결괏값을 알아낼 수 있습니다.

 

소스코드

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <vector>
#include <algorithm>
#define NMAX 18
#define MAX 0x7FFFFFFFFFFFFFFF
#define lint long long int
using namespace std;
 
lint N, t, X, Y;
vector< lint > A, B;
 
lint ret;
lint dp[NMAX][1<<NMAX];
 
lint sv(int idxB, int check) {
    if(idxB == N) return 0;
    else {
        if(dp[idxB][check] >= 0) return dp[idxB][check];
        else {
            int cnt=0;
            lint ret=0x7FFFFFFFFFFFFFFF;
 
            for(int idxA=0;idxA<N;idxA++) {
                if(check & (1<<idxA)) continue;
 
                // curA: idxA의 현재 위치 > idxB: 이미 왼쪽에 위치한 숫자 개수 / cnt: 사용하지 않은 숫자 개수(순번)
                // >> 자리를 바꾼 횟수를 구하기 위해 필요함
                int curA = idxB+cnt;
                ret = min( ret, sv(idxB+1, check|(1<<idxA)) + abs(idxB-curA)*Y + abs(A[idxB]-B[idxA])*X );
 
                cnt++;
            }
 
            return dp[idxB][check] = ret;
        }
    }
}
 
int main() {
    // input
    scanf("%lld %lld %lld", &N, &X, &Y);
    for(int i=0;i<N;i++) {
            scanf("%lld", &t);
            A.push_back(t);
    }
    for(int i=0;i<N;i++) {
            scanf("%lld", &t);
            B.push_back(t);
    }
 
    // DP
    memset(dp, -1, sizeof(dp));
    printf("%lld", sv(0, 0));
}
/*
3 4 10
20 3 40
40 3 20
ans: 30
 
4 3 5
4 2 5 2
6 4 2 1
ans: 16
*/

후기

아쉬움이 많이 드는 문제입니다. 콘테스트 과정에서 추상화 과정을 잘못하여 여러번 틀렸고, 끝나고 나서야 잘못된 점을 깨닫게 되었던 문제입니다. DP 문제답게 구현보다는 추상화 과정이 더욱 중요했던 문제입니다. DP 문제를 좋아하는 사람에게 한번쯤 권할 만한 문제라고 생각합니다.