[C/C++] 백준 3056번 - 007 (비트마스킹, DP)

 

 

<코드>

#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;

int N, cnt, tmp;
double agent[20][20];
double ans[1 << 20] = {1,};

int main() 
{
    cin >> N;

    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            cin >> agent[i][j];

    cout.precision(6); // 소수점 6자리까지 표현
    cout << fixed; // 소수점을 고정시켜 표현


    for (int i = 0; i < (1 << N); i++)
    {
        cnt = 0;
        tmp = i;
        while (tmp > 0) // 비트 수 세기
        {
            if (tmp % 2 == 1) cnt++;
            tmp /= 2;
        }
        
        for (int j = 0; j < N; j++)
        {   
            if((i&(1<<j)) == 0) // i 비트와 1<<j 비트가 겹치는 곳이 없을 때
               ans[i|(1<<j)] = max(ans[i|(1<<j)], ans[i]*agent[j][cnt]/100.0);   
        }
    }
    cout << ans[(1 << N) - 1] * 100 << endl;
}

 

풀이 방법

 

비트마스킹을 할 때 수행한 미션은 1, 수행하지 않은 미션은 0으로 표시합니다.

예를 들어 비트마스크 [0001]의 뜻은 첫 번째 지미가 미션 1을 수행을 하였다는 뜻입니다.
마찬가지로 [0100]의 뜻은 첫번째 지미가 미션 3을 수행하였다는 뜻입니다.

그리고 비트마스크에서 1의 개수를 cnt라 할 때 해당 비트마스크는 cnt번째의 지미가 미션을 수행한다는 뜻입니다.
예를 들어 [0011]의 경우는 두 번째 지미 본드가 수행한 것입니다.

for (int i = 0; i < (1 << N); i++)
    {
        cnt = 0;
        tmp = i;
        while (tmp > 0) // 비트 수 세기
        {
            if (tmp % 2 == 1) cnt++;
            tmp /= 2;
        }
        
        for (int j = 0; j < N; j++)
        {   
            if((i&(1<<j)) == 0) // i 비트와 1<<j 비트가 겹치는 곳이 없을 때
               ans[i|(1<<j)] = max(ans[i|(1<<j)], ans[i]*agent[j][cnt]/100.0);   
        }
    }

코드에서 for문은 i경우 0000~0111 까지 움직이며 각각의 i에서 j는 1부터 N-1까지 움직입니다.

for문의 과정을 아래에 나타내보면 (취소선을 친 부분은 if문의 조건에 맞지 않는 부분입니다.)

 

i = 0000 = 0 이면
1<<j = 0001 이고 ans[0001] = max(ans[0001], ans[0000] * agent[0][0] / 100.0);
1<<j = 0010 이고 ans[0010] = max(ans[0010], ans[0000] * agent[1][0] / 100.0);
1<<j = 0100 이고 ans[0100] = max(ans[0100], ans[0000] * agent[2][0] / 100.0);

i = 0001 = 1 이면
1<<j = 0001 이고 ans[0001] = max(ans[0001], ans[0001] * agent[0][1] / 100.0); X
1<<j = 0010 이고 ans[0011] = max(ans[0011], ans[0001] * agent[1][1] / 100.0);
1<<j = 0100 이고 ans[0101] = max(ans[0101], ans[0001] * agent[2][1] / 100.0);

i = 0010 = 2 이면
1<<j = 0001 이고 ans[0011] = max(ans[0011], ans[0010] * agent[0][1] / 100.0);
1<<j = 0010 이고 ans[0010] = max(ans[0010], ans[0010] * agent[1][1] / 100.0); X
1<<j = 0100 이고 ans[0110] = max(ans[0110], ans[0010] * agent[2][1] / 100.0);

i = 0011 = 3 이면
1<<j = 0001 이고 ans[0011] = max(ans[0011], ans[0011] * agent[0][2] / 100.0); X
1<<j = 0010 이고 ans[0011] = max(ans[0011], ans[0011] * agent[1][2] / 100.0); X
1<<j = 0100 이고 ans[0111] = max(ans[0111], ans[0011] * agent[2][2] / 100.0);

i = 0100 = 4 이면
1<<j = 0001 이고 ans[0101] = max(ans[0101], ans[0100] * agent[0][1] / 100.0);
1<<j = 0010 이고 ans[0110] = max(ans[0110], ans[0100] * agent[1][1] / 100.0);
1<<j = 0100 이고 ans[0100] = max(ans[0100], ans[0100] * agent[2][1] / 100.0); X

i = 0101 = 5 이면
1<<j = 0001 이고 ans[0101] = max(ans[0101], ans[0101] * agent[0][2] / 100.0); X
1<<j = 0010 이고 ans[0111] = max(ans[0111], ans[0101] * agent[1][2] / 100.0);
1<<j = 0100 이고 ans[0101] = max(ans[0101], ans[0101] * agent[2][2] / 100.0); X

i = 0110 = 6 이면
1<<j = 0001 이고 ans[0111] = max(ans[0111], ans[0110] * agent[0][2] / 100.0);
1<<j = 0010 이고 ans[0110] = max(ans[0110], ans[0110] * agent[1][2] / 100.0); X
1<<j = 0100 이고 ans[0110] = max(ans[0110], ans[0110] * agent[2][2] / 100.0); X

따라서 ans[0111] 에는 가장 높은 미션 성공률이 저장됩니다.

 

이해를 돕기위해 위의 과정중에서 i가 4일때 (i = 0100) 일때를 살펴보면

i = 0100 = 4 이면
1<<j = 0001 이고 ans[0101] = max(ans[0101], ans[0100] * agent[0][1] / 100.0); 
1<<j = 0010 이고 ans[0110] = max(ans[0110], ans[0100] * agent[1][1] / 100.0); 
1<<j = 0100 이고 ans[0100] = max(ans[0100], ans[0100] * agent[2][1] / 100.0); X 

ans[0100]는 첫번째 지미가 미션3을 수행한 것 입니다. 따라서 두번째 지미는 자동적으로 미션3을 클리어할 수 없고,
j가 3일 때 즉, (1<<j) == (1<<3) == 0100 인 경우는 if문의 조건에 의해 제외됩니다.

 

1<<j = 0001 이고 ans[0101] = max(ans[0101], ans[0100] * agent[0][1] / 100.0); 

i가 0100이므로 ans[0101]는 두번째 지미가 미션1을 수행한 것입니다. max함수로 최대값을 업데이트 해줍니다. 

 

 1<<j = 0010 이고 ans[0110] = max(ans[0110], ans[0100] * agent[1][1] / 100.0);

i가 0100이므로 ans[0110]는 두번째 지미가 미션2를 수행한 것입니다. max함수로 최대값을 업데이트 해줍니다. 

이런식으로 쭉쭉 구하다보면 모든 미션을 성공할 수 있는 최대의 성공률을 구할 수 있게 됩니다.

 

 

 

www.acmicpc.net/problem/3056

3056번: 007

 

 

 

문제가 어려워 풀이법을 참고한 블로그 - beginthread.tistory.com/50