알고리즘/알고리즘 공부 내용 정리

백준 BOJ 24486번 : Counting Haybales 풀이 (Diamond II, DP)

restudy 2022. 11. 10. 17:07
반응형

백준 BOJ 24486번 : Counting Haybales

문제 난이도 : Diamond II

알고리즘 분류 : DP

 

 

N개의 자연수가 주어지고, 크기 차이가 1인 인접한 두 수를 서로 swap할 수 있다고 할 때, 만들 수 있는 서로 다른 수열의 개수를 구하는 문제이다.

 

문제의 풀이는 USACO 사이트를 참고하였다.

 

 

 

먼저 관찰을 통해 알 수 있는 사실은 홀짝성이 같은 수들끼리는 순서가 바뀔 수 없다는 것이다.

(이것은 오직 크기 차이가 1인 인접한 두 수만 교환이 가능하므로, 홀짝성이 같은 = 크기가 2 이상 차이나는 수는 서로 위치가 바뀔 수 없기 때문이다.)

원래 정석적인 풀이는 이 사실을 이용하여 그래프의 단방향 간선들을 만들 수 있으므로, 위상 정렬로 푸는 풀이로 보인다.

 

아무튼 홀짝성을 활용하여 문제를 풀이하기 위해, dp[i][j]를 수열의 앞 부분 i+j개의 수들 중 i개의 짝수와 j개의 홀수가 나타나는 길이 i+j인 서로 다른 수열의 개수라고 하자.

 

이제 점화식을 만들기 위해 다음의 값들을 구해보자.

 

olp[j'] : inversion 불가능한 i'번째 홀수와 j'번째 짝수(홀수가 왼쪽)가 있을 때, j'번째 짝수에 대해 가능한 odd's leftmost position

elp[j'] : inversion 불가능한 i'번째 짝수와 j'번째 홀수(짝수가 왼쪽)가 있을 때, j'번째 홀수에 대해 가능한 even's leftmost position

(inversion 불가능하다는 것은 두 수의 차가 1보다 큰 경우를 의미한다.)

 

N이 5,000 이하로 충분히 작으므로 O(N^2) 시간에 이중 for문으로 모든 쌍들에 대해 검사하여 olp와 elp 값들을 구할 수 있다.

olp[j'] : j'번째(= num[j]) 짝수 왼쪽에 있을 수 있는 홀수의 가장 왼쪽 번호 (max로 갱신하면서 왼쪽 임계값을 오른쪽으로 좁혀나감)

elp[j'] : j'번째(= num[j]) 홀수 왼쪽에 있을 수 있는 짝수의 가장 왼쪽 번호 (max로 갱신하면서 왼쪽 임계값을 오른쪽으로 좁혀나감)

 

이제 모든 이제 모든 i번째 짝수와 j번째 홀수에 대해 O(even x odd) 시간에 dp값을 계산해주면 된다. (even : 짝수 개수, odd : 홀수 개수)

 

j번째 홀수가 olp[i] = i번째 짝수 왼쪽에 있을 수 있는 홀수의 가장 왼쪽 번호와 같거나 오른쪽에 있는 경우, dp[i][j] += dp[i-1][j]가 성립한다.

반대로 i번째 짝수가 elp[j] = j번째 홀수 왼쪽에 있을 수 있는 짝수의 가장 왼쪽 번호와 같거나 오른쪽에 있는 경우에도, dp[i][j] += dp[i][j-1]이 성립한다.

 

최종적으로는 dp[even][odd]가 답이 된다. (even : 짝수 개수, odd : 홀수 개수)

 

 

#include <bits/stdc++.h>
#define int long long
using namespace std;

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int T; cin >> T;

    while(T--) {
        int N; cin >> N;

        vector<int> v(N), num(N);
        int e = 0, o = 0;

        for(int i=0; i<N; i++) {
            cin >> v[i];

            if(v[i] % 2 == 0) num[i] = ++e;
            else if(v[i] % 2 == 1) num[i] = ++o;
        }

        vector<int> olp(e+1), elp(o+1);

        for(int i=0; i<N; i++)
            for(int j=i+1; j<N; j++)
                if(v[i] % 2 != v[j] % 2 && abs(v[i] - v[j]) > 1) {
                    if(v[j] % 2 == 0) olp[num[j]] = max(olp[num[j]], num[i]);
                    if(v[j] % 2 == 1) elp[num[j]] = max(elp[num[j]], num[i]);
                }

        vector<vector<int>> dp(e+1, vector<int>(o+1));
        dp[0][0] = 1;

        int mod = 1e9 + 7;

        for(int i=0; i<=e; i++)
            for(int j=0; j<=o; j++) {
                if(i > 0 && j >= olp[i]) dp[i][j] = (dp[i][j] + dp[i-1][j]) % mod;
                if(j > 0 && i >= elp[j]) dp[i][j] = (dp[i][j] + dp[i][j-1]) % mod;
            }

        int ans = dp[e][o];

        cout << ans << "\n";
    }
}

 

 

여담으로 FFT를 활용하면 이 문제를 O(N log N) 시간에도 풀이가 가능하다고 한다.

 

 

 

반응형