[DP]BOJ 1176_섞기

문제 링크 : https://www.acmicpc.net/problem/1176

1176번: 섞기

 

분할 정복을 이용한 아이디어 캐치가 중요한 문제이다.

문제의 상황은 N명을 줄세울 때, 줄을 서는 각 학생들의 양 옆 학생들과의 키 차이를 K 초과로 만들고 싶은 상황이다.

가능한 모든 경우를 보려면 최대 경우의 수가 16!로, 무려 조 단위의 수이므로 불가능하다.

 

N명을 줄 세우는 과정을 생각해보자.

지금까지 내가 몇 명을 세웠던 관계없이, 학생 한 명을 지금 세워져 있는 줄에 추가해 세우는 것은

현재까지 세워져 있는 줄의 맨 끝에 서 있는 학생과의 키 차이가 K 초과인지만 확인하면 되는 작업이다.

분할해서 생각한 문제

따라서 이 문제를 DP로 풀 때, 지금까지 줄을 선 학생들에 대한 정보와 맨 마지막에 선 학생의 정보가 필요할 것이다.

즉, DP[현재까지 줄 선 학생들(State)][맨 마지막 학생의 번호] 로 표현할 수 있다.

현재까지 줄을 선 학생들의 State는 그 학생들이 어떤 순서로 줄을 서 있는지는 나타낼 필요가 없다.

지금까지 누가 섰는지, 누가 안 섰는지에 대한 정보만 필요하기 때문이다.

따라서, 이는 비트마스크(bitmask) 를 통해 나타낼 수 있을 것이다.

비트마스크로 줄의 상태를 나타내면, 가능한 최대 State의 수는 2의 16제곱이므로 65536 번의 계산만 하면 된다.

16!에 비해 현저히 작은 계산 횟수를 가짐을 확인할 수 있다.

비트마스크 : https://4legs-study.tistory.com/5

Bitmask 에 대해

그렇다면 DP 배열 안의 값에는 무엇이 들어가야 할까? 바로 경우의 수이다.

즉, dp[State][Number] 의 값은 State에서 1로 표현된 학생들이 줄을 섰을 때,

Number 번째 학생이 끝에 오는 경우의 수 인 것이다.

 

키가 각각 1, 2, 3, 4, 5인 학생들을 키차이 1 초과로 세우는 상황일 때,

1번, 3번, 5번을 세우고 끝에 1번이 서는 경우의 수는 2가지이다. 따라서 dp[10101][1] = 2로 나타낼 수 있다.

이 상황에서 4번 학생을 추가로 줄 세울 때, 1번을 제외한 기존 줄의 3, 5번이 어떤 순서로 섰는지와는 상관없이

dp[10101][1] 의 각 경우 모두 dp[11101][4] 로 이어질 수 있다.

 

번호가 m인 끝 학생과의 키 비교를 통해 n번 학생을 새로 줄 세울 수 있다면,

n번을 세우기 전까지의 모든 경우의 수가 n번 학생을 포함한 State에서 끝에 n번이 오는 경우에 더해진다.

즉, if(키 차이가 K 초과라면) dp[newState][n] += dp[State][m] 으로 나타낼 수 있다.

 

[코드]

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <memory.h>
 
using namespace std;
int n, k, height[17];
int fullstate;
long long dp[1 << 17][17];            //dp[누구누구가 섰나?][마지막 사람은 누구?] : 해당 조합에서 가능한 경우의 수
 
void getDP() {
    //모든 State에 대해
    for (int i = 1; i <= fullstate; i++) {
        //각 State에서 마지막으로 j번이 설 수 있는 경우의 수를 체크한다.
        for (int j = 1; j <= n; j++) {
            //도달할 수 없는 Case 라면 건너뜀.
            if (dp[i][j] == 0) continue;
            //현재 State에서 m번을 세우는 것이 가능하다면, i상태의 j가 마지막인 경우의 수를 모두 m을 마지막으로 세운 새로운 State에 더해줌.
            for (int m = 1; m <= n; m++) {
                int newstate = i | 1 << (m - 1);
                if(!(i & 1 << (m - 1)) && abs(height[j] - height[m]) > k) dp[newstate][m] += dp[i][j];
            }
        }
    }
}
 
void init() {
    cin >> n >> k;
 
    memset(dp, 0, sizeof(dp));
 
    for (int i = 1; i <= n; i++) {
        int state = 1 << (i - 1);
        cin >> height[i];
        dp[state][i] = 1;
    }
    fullstate = (1 << n) - 1;
}
 
int main() {
    init();
 
    getDP();
 
    long long answer = 0;
    for (int i = 1; i <= n; i++) answer += dp[fullstate][i];
    
    printf("%lld\n", answer);
 
    //system("PAUSE");
    return 0;
}