백준 1102번 발전소

문제 링크입니다: https://www.acmicpc.net/problem/1102

비트마스킹과 DP를 적절히 이용해야지만 풀 수 있는 문제였습니다.

발전소의 상태가 string으로 주어지지만 'Y' = 1, 'N' = 0으로 바꾸어서 비트 형태로 표현하면 메모이제이션을 할 수 있기 때문에 비트마스킹을 이용했습니다.

알고리즘은 아래와 같습니다.

1. P가 0일 때는 발전소를 고치지 않아도 되기 때문에 비용이 0입니다.

2. 현재 작동되는 발전소에 대해서만 minCost 함수를 호출합니다.

i) 0 ~ (N-1) 발전소 중 고장난 발전소를 찾습니다.

ii) 고장난 발전소를 고치고 발전소의 상태를 업데이트합니다.

iii) 업데이트 된 상태에서 고장나지 않은 발전소에 대해서 2번을 반복합니다.

*풀긴 풀었지만 이해가 가지 않는 부분이 있습니다.

1. 우선 MAX = 16으로 지정할 경우 런타임 에러가 뜹니다. 런타임 에러가 뜨는 이유는 접근할 수 없는 인덱스에 접근했을 때 보통 발생하는데 반복문을 항상 N 전까지 돌리기 때문에 런타임 에러가 뜨는 이유를 모르겠습니다. 

-> MAX = 16 + 1로 수정했더니 해결

2. if ((nextState & (1 << j))) //해당 발전소를 킨 다음 단계로 이동 이 부분을 if ((nextState & (1 << j)) == 1) //해당 발전소를 킨 다음 단계로 이동 로 작성할 경우 오답처리가 됩니다. a & b 의 결과물은 a 와 b가 동시에 참이면 참, 둘 중 하나라도 거짓이면 거짓을 반환하기 때문에 0 혹은 1만 반환하는 줄 알았는데 아닌 것 같습니다...

-> 이 부분은 해결되었습니다.

*countSetBits 함수는 https://www.geeksforgeeks.org/count-set-bits-in-an-integer/를 참고했습니다!

*조건 충족에서 -1을 하는 이유는 최초 비트를 (1 << MAX) 로 잡았기 때문에 1이 이미 추가되어있는 상태이기 때문에 -1을 했습니다.

#include <iostream>

#include <string>

#include <algorithm>

#include <cmath>

#include <cstring> //memset

using namespace std;

 

const int MAX = 16 + 1;

const int INF = 987654321;

 

int N, P;

string currentState;

int bit = 1 << MAX;

int fixCost[MAX][MAX];

int cache[MAX][1 << MAX]; //몇 번째 발전소, 발전소 가동상태

 

//비트 내 1 세는 법

int countSetBits(int n)

{

        int count = 0;

        while (n)

        {

                 count += n & 1;

                 n >>= 1;

        }

        return count;

}

 

int minCost(int idx, int curState)

{

        //조건 충족

        if (countSetBits(curState) - 1 >= P)

                 return 0;

 

        int &result = cache[idx][curState];

        if (result != -1)

                 return result;

 

        result = INF;

        for (int i = 0; i < N; i++)

                 if ((curState & (1 << i)) == 0) //꺼진 발전소를 찾고

                 {

                         int nextState = curState | (1 << i); //해당 발전소를 켰다고 가정

                         for (int j = 0; j < N; j++)

                                 if ((nextState & (1 << j))) //해당 발전소를 킨 다음 단계로 이동

                                          result = min(result, fixCost[idx][i] + minCost(j, nextState));

                 }

        return result;

}

 

int main(void)

{

        cin >> N;

 

        for (int i = 0; i < N; i++)

                 for (int j = 0; j < N; j++)

                         cin >> fixCost[i][j];

 

 

        cin >> currentState;

        for (int i = 0; i < currentState.size(); i++)

                 if (currentState[i] == 'Y')

                         bit |= (1 << i);

 

        cin >> P;

 

        if (P == 0)

                 cout << 0 << endl;

        else

        {

                 memset(cache, -1, sizeof(cache));

                 int result = INF;

                 for (int i = 0; i < N; i++)

                         if (currentState[i] == 'Y')

                                 result = min(result, minCost(i, bit));

 

                 if (result == INF)

                         cout << -1 << endl;

                 else

                         cout << result << endl;

        }

        return 0;

}

 

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~