[Codeup] 2748. 덧셈, 뺄셈으로 n만들기

1. 문제 링크

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

코드업

 

2. 문제 풀이

탐색의 범위인 n이 0 <= n <= 20이다.

여기서 유의해야 할 점은 n이 0일수도 있다는 점이다.

 

문제에서 '숫자 0에서 n개의 수를 덧셈과 뺄셈을 이용하여 m으로 만드려고 한다.'라고 했다.

n이 0일때는 덧셈과 뺄셈의 이용이 불가능하기 때문에, 숫자 m을 만드는 방법은 0일때 딱 1가지다.

m이 0이 아닌 숫자일때는 방법이 없는 것으로 봐야 할 것 같다.

 

즉, 연산을 하지 않은 상태로 하나의 유효한 경우로 간주해야 한다.

 

이외의 경우는 n의 범위가 크지 않기 때문에, 모든 경우에 대해서 덧셈, 뺄셈을 해 나가며 탐색 시켜준다.

 

3. 아이디어

1. n == 0일때는 m의 값에 따라 1또는 0으로 처리한다.
2. 나머지 케이스의 경우 재귀 탐색 기반 완전 탐색을 진행한다.
    depth 형태로 0번째 값 부터 탐색하여, n-1에 도달했을때 그 결과 값이 m이면, m을 만들 수 있다.
    n-1에 도달했을때 m이 만들어지지 않으면, m을 만들 수 없는 값이다.
3. 이 경우를 각각 덧셈, 뺄셈 형태로 나눠서 모든 경우를 탐색 시키도록 처리한다.

4. 구현

※ C++ Source Code

#include <iostream>
using namespace std;
int m, n;
int value[25];
int ans = 0;
void back(int sum, int pos)
{
	int temp = sum;
	if (pos == n - 1) // 끝 도달
	{
		if (temp == m) // m을 만든 경우
		{
			ans++;
		}
		return;
	}
	
	back(temp + value[pos + 1], pos + 1); // 다음 값에 덧셈 사용
	back(temp - value[pos + 1], pos + 1); // 다음 값에 뺄셈 사용
}
int main(void)
{
	cin >> m;
	cin >> n;
	if (n == 0) // 0개의 수를 이용했을때
	{
		if (m == 0)
		{
			ans = 1;
			cout << ans; // 단 하나도 이용하지 않았지만 0을 만드는 것 자체는 가능
			return 0;
		}
		else
		{
			ans = 0;
			cout << ans; // 단 하나도 이용하지 않았지만 0을 만드는 것 자체는 가능
			return 0;
		}
	}

	for (int i = 0; i < n; i++)
	{
		cin >> value[i];
	}
	back(value[0], 0); // 맨 앞 값에 덧셈
	back(-value[0], 0); // 맨 앞 값에 뺄셈
	
	cout << ans;
}