[C++ / 백준 1182번] 부분 수열의 합

문제

 

 

 

시행 착오

 

비트마스크 사용법을 몰라 인터넷에 검색해 이해했다. 비트 연산을 통해 백트래킹 사용을 하거나 큰 크기의 배열을 선언할 필요 없이 간편하게 해결할 수 있었다.

 

비트마스크는 아래 글을 읽고 이해했다.

 

https://velog.io/@alkwen0996/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%B9%84%ED%8A%B8%EB%A7%88%EC%8A%A4%ED%81%AC

[알고리즘] | 비트마스크

 

비트마스크 풀이의 좋은 점은 O(1) 시간에 계산이 가능하다는 점이다. 실행 시간이 빨라지고 메모리도 적게 사용하며, 집합을 이용해 0부터 1<<N -1 까지의 경우의 수를 비트연산을 이용해 전부 체크해볼 수 있다. 어떤 문제에서는 백트래킹보다 효율적인듯 하다.

 

 

 

해결 방법

 

비트마스크 사용 X (백트래킹만 사용) 

 

#include <iostream>
using namespace std;

int N, S, cnt = 0;
int s[21];

void recur(int ind, int cursum)
{
    if (ind == N)  // 종료 조건: 모든 원소를 탐색했을 때
    {
        if (cursum == S) cnt++;
        return;
    }

    // 현재 원소를 선택하는 경우
    recur(ind + 1, cursum + s[ind]);

    // 현재 원소를 선택하지 않는 경우
    recur(ind + 1, cursum);
}

int main() {
    cin.tie(NULL);
    ios::sync_with_stdio(false);

    cin >> N >> S;

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

    recur(0, 0);

    // 공집합 제거 (S == 0일 때, 아무것도 선택하지 않은 경우 포함됨)
    if (S == 0) cnt--;

    cout << cnt;
    return 0;
}

 

 

비트마스크 사용

 

#include <iostream>
using namespace std;

int N, S, cnt = 0;
int s[20];

int main() {
    cin.tie(NULL);
    ios::sync_with_stdio(false);

    cin >> N >> S;

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

    for (int i = 1; i < (1 << N); i++)
    {
        int sum = 0;
        for (int j = 0; j < N; j++)
        {
            if (i & (1 << j))
            {
                sum += s[j];
            }

           
        }

        if (sum == S)
        {
            cnt++;
        }
    }


    cout << cnt;



    return 0;
}