전공책

예상 난이도 : 5 / 10

이번 문제는 '전공책'(https://www.acmicpc.net/problem/16508) 입니다.

이 문제가 좋다고 생각하는 이유는 '비트 연산에 대해서 연습, 완전 탐색을 다른 방식으로 접근하는 방법을 연습,

최적화하는 방법에 대한 연습'을 해볼 수 있어서 입니다.

이 문제는 '완전탐색' 문제입니다.

전공책의 갯수가 16개밖에 되지 않습니다. 모든 조합을 다 만들어봐도 2^16개 정도밖에 되지 않으니

다 해봐도 무방합니다. 조건을 조금 추가해서 최적화 시킬 수도 있습니다.

우선 이런 작은 수의 완전탐색을 푸는 간단한 방법은 비트맵을 이용하는 겁니다.

int 변수는 총 32비트로 32개 원소를 완전탐색할 때 쓸 수 있습니다. 원소의 갯수가 더 많다면 long long이나

배열까지 쓸 수 있겠죠. 하지만 그렇게 많은 수를 완전탐색하려면 시간이 많이 소모되기 때문에 그런 문제일 경우

DP로 풀 수 있지 않은가 생각해봐야겠죠.

for (int i = 1; i <= (1 << n) - 1; i++){
        for (int j = 0; j < n; j++) {
            if ((i&(1 << j)) == 0) continue;
           
        }
}

기본 뼈대는 위 코드입니다. i를 1부터 시작한 것은 아무것도 안고른 0의 상황은 고려하지 않아도 되므로 제외시킨 것 입니다.

이렇게 i 값이 1부터 (1<<n)-1 까지 돈다는 소리는 뭘까요.

i가 3비트 변수이고 n이 3이라고 가정해보고 시뮬레이션 해보겠습니다.

001

010

011

100

101

110

111

i값이 이렇게 됩니다. 각 비트를 원소라고 생각한다면, 3가지 원소의 모든 조합이 나타나는게 보이시나요?

이런 식으로 간단하게 완전 탐색을 할 수 있습니다!! 

재귀 함수만 썼던 저에게 충격적인 해법이었죠...

이 문제를 물론 재귀함수로 완전탐색해서 풀 수 있습니다.

그건 입력이 훨씬 큰 다른 문제에서 다루도록 하겠습니다. 

각 경우에서 이제 안에 있는 for문을 보면 각 비트에서 &연산을 취하면서 이 원소가 선택된 것인지를 확인하고 

처리해주는 로직이 들어갑니다. 재귀 함수 이런 연산 없이 한 번에 확인이 가능하지만요.

비트 연산자는 실행시간이 가장 빠르고 부담이 거의 없기 때문에 실행 시간 면에서 여러모로 이득을 볼 수 있습니다.

각 전공책을 고르는 모든 경우에서 원하는 글자를 모두 커버하면서 가장 싼 경우를 저장해서 출력하면 끝.

최적화) 

위와 같은 방식으로 접근하면 필요없는 경우까지 모두 조사하므로 시간이 꽤 걸립니다. (물론 제한시간보다 한참 적지만요)

"어떻게 최적화할 수 있을까요?"

PS 경험이 많은 분들이시라면 스스로에게 많이 하는 질문일 거라고 생각합니다.

저는 한참 하수이기에 이런 물음을 많이 하는 것일 수도 있겠네요 ㅎㅎㅎ

이런 질문은 "필요없는 경우의 수는 무엇일까, 그리고 이것을 어떻게 걸러낼까?" 로 바꿔볼 수 있습니다.

이 문제에서 필요없는 경우는 무엇일까요? '필요없는 전공책을 산 경우'입니다.

이 비트 연산에서 가장 단점이라고 할 수 있는 것 중 하나는 '원소의 갯수'를 편하게 조정할 수가 없다는 점 입니다.

물론 어떻게든 구현은 가능하지만, 귀찮다는 것입니다.

그 비효율성은 눈감아준다면, 내가 원하는 전공책을 고른 경우에 따로 벡터로 만들어 i 값을 push_back 해줍니다.

        bool redo = false;
        for (int k : st) {
            if ((i&k) == k) {
                redo = true;
                break;
            }
        }
 
        if (redo) continue;
 

위 코드는 st 라는 벡터를 만들고 답 후보일 때마다 i 값을 저장합니다. 그리고 그 다음 i 값을 검사합니다.

3번째 줄이 핵심입니다. &연산을 취해서 이미 저장해둔 답 후보와 일치할 경우!!!

이 뜻은 : 이번에 시도하려고 하는 i는, 이미 답 후보에 있는 녀석에 쓸모없는 전공책을 더 산 경우니까 시도하지마.

이렇게 최적화 해줄 수 있습니다.

완벽한 최적화가 아닙니다. 차근차근 전공책의 갯수를 늘려가는 탐색이 아니므로 쓸모없는 책을 산 경우도 고려해주게 됩니다.

귀찮지만, 이런 경우까지 최적화 시킬 수는 있습니다. 한 번 해보시길..