목록백트래킹 (1)
잡동사니 기랸씨
[백준/C++] 1182: 부분수열의 합
정보 이름: 부분수열의 합 난이도: Silver 2 알고리즘 브루트포스 알고리즘 백트래킹 해설 우선 수열이 될 배열에 입력 값들을 저장합니다. 그 후, 배열을 앞에서부터 순회하며 부분 수열을 만듭니다. 부분 수열의 합이 S와 같다면 cnt를 1 증가시킵니다. 문제에서 공집합을 제외(크기가 양수인 부분수열)하라고 하니 공집합의 합인 S == 0 인 경우 cnt를 1 감소시킵니다. 코드 #include using namespace std; int n, s, cnt; int nums[25]; int isUsed[25]; void solve(int sum, int idx) { if (idx == n) { if (sum == s) cnt++; return; } solve(sum + nums[idx], idx + ..
공부/알고리즘
2023. 2. 6. 12:03