코드업 3009번

이 글에서는 코드업 3009번 문제를 풀이해보도록 하겠습니다.

https://codeup.kr/problem.php?id=3009 

부분수열의 합

---

문제 설명

 

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

---

입력

 

첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 <= N <= 20, |S| <= 1,000,000)

둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절대값은 100,000을 넘지 않는다. 같은 수가 여러번 주어질 수도 있다.

---

출력

 

첫째 줄에 합이 S가 되는 부분수열의 개수를 출력한다.

문제를 해석해보면, 정수 N개가 주어질텐데 이들 중 임의로 몇 개를 더해서 정수 S를 만드려고 할 때 가능한 경우의 수를 묻는 문제입니다. 모든 경우의 수를 다 계산해보고 계산 결과가 S인 경우를 세는 방식으로 풀이하고자 하였습니다.

먼저 순서도를 그려보았습니다.

전체 과정 순서도입니다.

핵심이 되는 함수 f의 순서도입니다.

이를 바탕으로 코드를 짜보았습니다.

#include <stdio.h>

int n, s;
int a[50];
int cnt = 0;

void f(int k, int tf, int sum)
{
	sum = sum + a[k]*tf;
	
	if(k == n-1)
	{
		if(sum == s)
		{
			cnt++;
		}
		return;
	}
	else
	{
		f(k+1, 0, sum);
		f(k+1, 1, sum);
	}
}

int main()
{
	scanf("%d %d", &n, &s);
	for(int i = 0; i < n; i++)
	{
		scanf("%d", &a[i]);
	}
	
	f(0, 0, 0);
	f(0, 1, 0);
	printf("%d", cnt-(!s)*1);
}

사실 처음에는 마지막 printf 문에서 cnt를 출력하였습니다. 즉,

printf("%d", cnt);

로 작성하였습니다. 하지만, 만약 S가 0으로 주어졌을 때는 아무것도 더하지 않은 경우도 세버려서 1개가 더 세어지는 문제가 발생하였습니다. 즉, S가 0인 경우에는 cnt 값에서 1을 빼서 출력해야 올바른 결과를 얻을 수 있었습니다. 그래서 위와 같이 cnt-(!s)*1를 출력해줌으로써 이 문제를 해결해주었습니다.

그러면 대략적인 코드 설명을 해보겠습니다.

n과 s를 입력받고, n개의 정수를 입력받아 배열 a에 저장합니다. 이제 함수 f를 실행할 것인데, f에는 k, tf, sum 3개의 인자가 전달됩니다. k는 배열의 몇 번째 수를, tf는 더할 것인지(1) 아닌지(0), sum은 그 전까지 계산한 결과값을 의미합니다. k를 1씩 더해주고 tf가 0인 경우와 1인 경우 모두 실행해주어 가능한 경우를 모두 만들었고, k를 0부터 n-1까지 배열 a에 있는 모든 수에 대해 연산을 진행해주었습니다.

---

이렇게 코드업 3009번 문제를 풀이해보았습니다.