알고리즘 :: 백준 :: Bruteforce :: 1182 :: 부분수열의 합

Embedded June·2020년 7월 26일
0

알고리즘::백준

목록 보기
17/109

문제

N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오.

문제접근

  • 시간제한은 2초이고 정수의 개수 N은 1부터 20까지로 적은 범위가 주어졌음을 눈치챈다.
  • 간단히 a, b, c 3개의 숫자를 이용해서 만들 수 있는 덧셈 조합을 생각해보면 다음과 같다.
    • a, b, c, a+b, a+c, b+c, a+b+c
    • 나올 수 있는 조합의 개수는 2n12^n - 1개이므로 이 문제에 bruteforce를 적용할 경우 시간복잡도는 O(2n)O(2^n)이다.
    • 상한값 22012^{20} - 1 은 1,048,575이므로 시간제한 내에 충분히 풀 수 있음을 눈치챈다.
  • 위 사고과정을 거쳐서 우리는 이 문제에 bruteforce를 적용하고자 한다.
  • 재귀를 사용해서, i번째 인덱스의 요소를 더하는 경우와 더하지 않는 경우로 나눠서 전역탐색 하고자 한다.

코드

#include <iostream>
using namespace std;

static constexpr int MAX = 20;
static int N, S, result;
static int arr[MAX];

void solve(int idx, int sum){
	sum += arr[idx]; //우선 해당 숫자를 더한다
	if (idx >= N) return;		// [기저1] - 범위 초과시 return
	if (sum == S) result++;		// [기저2] - S를 찾은 경우 경우의 수 추가
	solve(idx + 1, sum - arr[idx]); // idx번 요소를 더하지 않는 경우
	solve(idx + 1, sum); 		// idx번 요소를 더하는 경우
}
int main() {
	cin >> N >> S;
	for (int i = 0; i < N; i++) cin >> arr[i];
	solve(0, 0);
	cout << result << endl;
}

결과

profile
임베디드 시스템 공학자를 지망하는 컴퓨터공학+전자공학 복수전공 학부생입니다. 타인의 피드백을 수용하고 숙고하고 대응하며 자극과 반응 사이의 간격을 늘리며 스스로 반응을 컨트롤 할 수 있는 주도적인 사람이 되는 것이 저의 20대의 목표입니다.

0개의 댓글