[5-W] 비트마스킹으로 풀어봤습니다!

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트

5-W

작성

268

#include <bits/stdc++.h>

using namespace std;

int N, nums[100010], res=INT_MIN;


int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> N;
    
    for(int i = 0 ; i < N ; i++){
        cin >> nums[i];
    }
    
    for(int i = 1 ; i < (1<<N) ; i*=2){ // 0001 0010 0100 1000
        
        for(int j = i; j < (1<<N) ; j=(j<<1)+i){ // 0001 0011 0111 1111
            
            int tmp=0;
            for(int k = 0 ; k < N ; k++){
                if(j & 1<<k){ // k 번째 숫자 사용 여부.
                    tmp+=nums[k];
                }
            }
            res = max(res, tmp);
        }
    }
    
    
    cout << res << '\n';
}

안녕하세요 큰돌님

비트마스킹으로 풀어봤습니다만.. 이미 시간초과입니다.

그래도 시간초과라도 나오는 지 보려고 넣어봤는데 그냥 틀렸습니다라고만 떠서 반례를 찾아보려하는데 찾기가 어렵네요 ㅠㅠ

이 논리에 어느 부분이 문제인지 궁금합니다 ㅠㅠ

c++코딩-테스트

답변 2

큰돌

지식공유자

안녕하세요 태승님 ㅎㅎ

음.. 일단 접근법이 잘못된거 같아요.

첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.

문제의 범위를 보시면.. 10만인데요.

비트마스킹으로 모든 경우의 수를 고려한다고 치면요 2^n이기 때문에 너무나도 큰 수가 되구요.

그리고. 이 문제는 연속적인 수의 합을 구하는 문제이기 때문에 비트마스킹으로 풀면 안됩니다.

예를 들어 101이런식으로 경우의 수를 따진다고 치면

0번째 2번째 연속되지 않은 수의 합이 생겨버리는데 이런 로직에다 필터링을 하는 것은 너무나도 비효율적입니다.

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제가 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.

정태승

질문자

감사합니다 ㅠㅠ 접근법이 틀렸군요오

인프런 커뮤니티 질문&답변

[5-W] 비트마스킹으로 풀어봤습니다!