본문 바로가기
알고리즘 문제풀이/백준

[백준 1182] 부분수열의 합

by m2162003 2020. 11. 5.

www.acmicpc.net/problem/1182

 

1182번: 부분수열의 합

첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다.

www.acmicpc.net

벡터를 사용하지 않고 풀어보기!

s=0일 경우 하나도 안더했을 때도 포함되므로 빼줘야 한다. 왜냐면 부분 수열의 크기가 양수이기 때문이다.

#include <stdio.h>

using namespace std;

int arr[21];
int n, s, answer;

void dfs(int idx, int sum)
{
  if (idx > n - 1)
  {
    if (sum == s)
    {
      answer++;
    }
    return;
  }

  dfs(idx + 1, sum + arr[idx]);
  dfs(idx + 1, sum);
}
int main(void)
{
  scanf("%d%d", &n, &s);

  for (int i = 0; i < n; i++)
  {
    scanf("%d", &arr[i]);
  }

  dfs(0, 0);
  if (s == 0)
  {
    answer--;
  }
  printf("%d\n", answer);
  return 0;
}

'알고리즘 문제풀이 > 백준' 카테고리의 다른 글

[백준 16987] 계란으로 계란치기  (0) 2020.11.12
[백준 14891] 톱니바퀴  (0) 2020.11.07
[백준 9663]N-Queen  (0) 2020.11.05
[백준 13335] 트럭  (0) 2020.11.04
[백준 13913] 숨바꼭질 4  (0) 2020.11.01

댓글