반응형
https://www.acmicpc.net/problem/1182
💡 부분수열의 합
N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오.
[입력]
첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다.
[출력]
첫째 줄에 합이 S가 되는 부분수열의 개수를 출력한다.
부분수열의 개념을 정확히 몰라서 처음에는 연속적인 수열을 생각했는데, 그냥 수열 내 부분집합이라 생각하면 된다.
단, 공집합은 제외한다.
✅ 문제 풀이
- 처음에는 visited 배열을 선언하고 방문 여부를 바꾸면서 백트래킹으로 해결하려했으나, 코드가 복잡하고 한눈에 안들어와서 매우 간단한 재귀함수 풀이로 바꾸었다.
- func(num, sum)라는 함수를 사용할 건데, num은 현재 수열에서 몇개까지 봤는지이고, sum은 수열에서 num번째 수를 포함하거나 포함하지 않은 값이다. 즉 누적 합이다.
- func()함수 내에서 만약 num이 N이면, 즉 끝까지 다 방문했을경우에, sum이 S와 같으면 answer를 하나 올려준다. 그리고 return을 통해 더이상 재귀가 일어나지 않도록 한다.
- 그리고 다음 값을 더하지 않는 경우 func(num+1, sum)와 다음 값을 더하는 경우 func(num+1, sum+arr[num])로 두번 호출하여 재귀를 이어나가도록 한다.
- 그림으로 나타내면 다음과 같다. 그림에서는 예제의 값으로 사용하였다.
수열의 num번째 값을 더한 쪽을 왼쪽, 안더한 쪽을 오른쪽으로 하여 가지치기 형태로 재귀를 호출하게 된다.
보면 맨 오른쪽의 아무것도 더하지 않는 공집합이 포함되어 있음을 알 수 있다.
- num은 0, sum은 0부터 시작한다.
- func(0,0)을 하고 나면 count 된 값이 answer가 된다.
- 주의할 점은, S가 0인 경우에, 공집합의 0도 count에 포함시켜버리므로, 이런 경우에는 answer를 하나 빼주면 된다.
✏ 코드 전문
#include<iostream>
using namespace std;
int N, S, answer=0;
int *arr;
void func(int num, int sum) {
if (num == N) {
if (sum == S) {
answer++;
}
return;
}
func(num + 1, sum);
func(num + 1, sum + arr[num]);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> N >> S;
arr = new int[N];
for (int i = 0; i < N; i++) {
cin >> arr[i];
}
func(0, 0);
if (S == 0) answer--;
cout << answer;
return 0;
}
반응형
'CO-TE > 백준' 카테고리의 다른 글
[백준] 1439번 C++ "뒤집기" 풀이 / 문자열처리 (1) | 2023.12.04 |
---|---|
[백준] 1475번 C++ "방 번호" 풀이 / 구현 (1) | 2023.12.03 |
[백준] 1074번 C++ "Z" 풀이 / 분할과 정복, 반복문 (1) | 2023.12.01 |
[백준] 2003번 C++ "수들의 합2" 풀이 / 누적합, 두 포인터 (1) | 2023.11.28 |
[백준] 1068번 C++ "트리" 풀이 / 그래프 탐색, DFS 알고리즘 (1) | 2023.11.26 |