-
백준 1182 (부분수열의 합)컴퓨터 공학 기초/알고리즘 (브루트포스) 2020. 8. 20. 03:58
https://www.acmicpc.net/problem/1182
해당 문제는 숫자 N 과 S 그리고 N개의 정수가 주어질 때 N개의 숫자를 조합하여 더했을 때 주어진 S가 나올 수 있는 모든 경우를 구하는 문제이다. 따라서 DFS를 이용한 조합을 추출하고 해당 조합의 총합이 S인지만 비교해주면 되는 문제이다.
이때 주의해야 할 점은 따로 조합의 크기는 없으므로 재귀가 수행 할 때마다 현재 선택된 수의 총합을 갱신하며 S값과 같은지 비교해 주어야 한다.
풀이 :
#include <iostream> #include <vector> using namespace std; int n, s, cnt; vector<int> nList; void dfs(int level, int idx, long long sum){ if (level == n) return; for (int i = idx; i < n; ++i){ if (sum + nList[i] == s) ++cnt; dfs(level + 1, i + 1, sum + nList[i]); } } int main(){ //freopen_s(new FILE*, "tes.text", "r", stdin); cin >> n >> s; for (int i = 0; i < n; ++i){ int tmp; cin >> tmp; nList.push_back(tmp); } dfs(0, 0, 0); cout << cnt << endl; }
'컴퓨터 공학 기초 > 알고리즘 (브루트포스)' 카테고리의 다른 글
백준 13023(ABCDE) (0) 2020.08.20 백준 1759 (암호 만들기) (0) 2020.08.19 백준 6603 (로또) (0) 2020.08.19 백준 10971 (외판원 순회 2) (0) 2020.08.19 백준 10819 (차이를 최대로) (0) 2020.08.19