[BOJ/백준] 14225 부분수열의 합

● [문제번호 14225] 부분수열의 합

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

14225번: 부분수열의 합

 

 

● 알아야 할 것

: 재귀

: 브루트 포스 (Brute Force)

 

 

● 풀이 과정

: 만들 수 있는 부분수열의 합을 체크하는 배열을 만들어 놓고

만들 수 있는 부분수열의 합을 모두 만들어본다.

 

그 다음 1부터 시작하여 못 만든 자연수를 찾아내 출력하면 된다.

 

 

● 주의 할 것

: NULL

 

 

● 참고 할 것

: NULL

 

 

● 풀이 코드

#include <bits/stdc++.h>

using namespace std;

// used : 부분 수열의 합이 나온 경우 체크
// S : 수열 S 입력
bool used[2000001];
int S[21];
int N;

// 부분 수열의 합 체크하기
void check(int index, int total)
{
    // S수열의 범위를 넘어선 경우
    if(N - 1 < index)
        return ;
    
    // 중복된 경우를 없애기 위해 index부터 시작
    for(int i = index; i < N; i++)
    {
        // 1. 수열 원소 더하고
        // 2. 체크하고
        // 3. 재귀
        // 4. 다시 빼고
        total += S[i];
        used[total] = true;
        check(i + 1, total);
        total -= S[i];
    }
}


int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin >> N;
    
    // 수열 입력
    for(int n = 0; n < N; n++)
        cin >> S[n];
    
    // 재귀 시작
    check(0, 0);
    
    // 만들수 없는 자연수 출력
    for(int i = 1; i < 2000001; i++)
    {
        if(!used[i])
        {
            cout << i;
            break;
        }
    }
    
    return 0;
}

 

 

● [백준] - [알고리즘 중급 1/3] - [531 - 브루트 포스 - 재귀 (연습)] 문제집

번호	문제 번호	문제 이름	풀이 링크
1	6603	로또	https://pirateturtle.tistory.com/301
2	1182	부분수열의 합	https://pirateturtle.tistory.com/302
3	14225	부분수열의 합	https://pirateturtle.tistory.com/303
4	14888	연산자 끼워넣기	https://pirateturtle.tistory.com/304
5	15658	연산자 끼워넣기 (2)	https://pirateturtle.tistory.com/305
6	14500	테트로미노	https://pirateturtle.tistory.com/306
7	16197	두 동전	https://pirateturtle.tistory.com/307
8	16198	에너지 모으기	https://pirateturtle.tistory.com/308
9	9663	N-Queen	https://pirateturtle.tistory.com/309
10	2580	스도쿠	https://pirateturtle.tistory.com/310
11	4574	스도미노쿠	https://pirateturtle.tistory.com/311
12	1987	알파벳	https://pirateturtle.tistory.com/312