[백준 1182] 부분수열의 합 - C++ / 시뮬레이션 알고리즘

문제

https://www.acmicpc.net/problem/1182

1182번: 부분수열의 합

nextnext_permutation

현재 나와 있는 수열에서 인자로 넘어간 범위에 해당하는 다음 순열을 구하고 true를 반환한다.

다음 순열이 없다면(다음에 나온 순열이 순서상 이전 순열보다 작다면) false를 반환.

첫번째 인자가 구하고자 하는 순열의 시작, 두번째 인자가 순열의 끝

bool next_permutation (BidirectionalIterator first, BidirectionalIterator last);

아래는 해당 함수를 이용한 "수열"을 구하는 코드이다.

#include <iostream>
#include <algorithm>
#include <vector>
 
using namespace std;
 
int main(void) {
    //array
    int a[4] = { 1,2,3,4 };
    do {
        for (int i = 0; i < 4; i++)
            cout << a[i] << ' ';
        cout << '\n';
    } while (next_permutation(a, a + 4));
 
    //vector
    vector<int> b = { 1,2,3,4 };
    do {
        for (int i = 0; i < 4; i++)
            cout << b[i] << ' ';
        cout << '\n';
    } while (next_permutation(b.begin(), b.end()));
}

그렇다면 4개의 숫자중 2개를 골라서 뽑으려면 어떻게 해야할까??

이는 먼저 next_permutation의 구조를 이해해야한다. -> redcoder.tistory.com/7

select라는 배열을 통해 해당 개수만큼 순열과 조합을 뽑을 수 있다.

아래는 "순열"에 해당하는 코드. 조합은 select = {0,0,0,1,1}식으로 작성되기만 하면 된다.

#include <iostream>
#include <algorithm>
#define MAX 8
 
using namespace std;
 
int n, m;
int arr[MAX]; //수열 숫자
int select[MAX]; //핵심!!!!!
 
void func() {
    do {
        int seq[MAX] = {}; //수열
        for (int i = 0; i < n; i++) {
            if (select[i]) {
                seq[select[i] - 1] = arr[i];
            }
        }
        
        for (int i = 0; i < m; i++)
            cout << seq[i] << ' ';
        cout << '\n';
    } while (next_permutation(select, select + n));
}
 
int main(void) {
    cin >> n >> m;
 
    select[m] = 1;
    for (int i = 0; i < n; i++) {
        arr[i] = i + 1;
        if (i > m)
            select[i] = select[i - 1] + 1 ;  // select = {0,0,1,2}
    }
    
    func();
}

 

나의 코드

#include <iostream>
#include <algorithm>
#define MAX 20
 
using namespace std;
 
int arr[MAX];
bool selected[MAX];
int n, s, result;
 
void part_sequence(int cnt) {
    for (int i = 0; i < n; i++) {
        if (i >= n - cnt)
            selected[i] = true; // ex. cnt = 2 : select = {0,0,0,1,1}
    }
 
    do {
        int total = 0;
        for (int i = 0; i < n; i++) {
            if (selected[i])
                total += arr[i];
        }
        if (total == s)
            result++;
    } while (next_permutation(selected, selected + n));
}
 
int main(void) {
    result = 0;
 
    cin >> n >> s;
    for (int i = 0; i < n; i++) {
        int a;
        cin >> a;
        arr[i] = a;
    }
 
    for (int i = 1; i <= n; i++) {
        part_sequence(i);
    }
 
    cout << result << '\n';
}

 

부분 수열을 구한다는 것 빼고는 그렇게 크게 다르지 않은 문제였다.

selected 배열을 왜 저렇게 초기화해야하는지에 대해 이해만 하면 문제 없을 것이다.