BOJ 1182 : 부분수열의 합 - C++
부분수열의 합
- 사실
백트래킹
보다는 재귀를 통한 완전탐색
의 느낌
--> 다시 돌아와서 새로운 경우를 찾지는 않고 base condition
에 도달할 때 까지 쭉 가는 형식이기 때문
코드
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int N, S, ans=0;
int arr[21];
void func(int idx, int sum){
/* 모든 요소는 전부 순회해서 돌긴 해야 한다
--> 이렇게 안하면 S가 0일때 바로 종료된다. */
if(idx == N){
if(sum == S){
ans++;
return;
}
}
else{
/* 자신을 포함했거나, 포함안했거나 2가지 경우의수 수행 */
func(idx+1, sum);
func(idx+1, sum+arr[idx]);
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> N >> S;
for(int i=0;i<N;i++)
cin >> arr[i];
func(0, 0);
if(S == 0) ans--;
cout << ans;
return 0;
}
- 주의할 점
1) 일단 모든 요소는 순회해야 한다
--> 그렇지 않으면 S가 0일때 경우 세지도 않고 바로 종료함
2) isused[]
불필요 !
isused[]
는 다시 돌아와서 사용의 여부에 따라 새로운 경우의 수를 돌게 하기 위해서 사용했음
하지만, 지금 문제는 그냥 자신을 포함하거나 포함하지 않거나 2가지 경우에 대해 재귀를 돌 뿐 돌아와서 새로운 경우의 수를 찾지는 않기에 isused[]
가 필요하지 않다.
Author And Source
이 문제에 관하여(BOJ 1182 : 부분수열의 합 - C++), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@neity16/BOJ-1182-부분수열의-합-C
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
- 사실
백트래킹
보다는재귀를 통한 완전탐색
의 느낌
--> 다시 돌아와서 새로운 경우를 찾지는 않고base condition
에 도달할 때 까지 쭉 가는 형식이기 때문
#include <iostream> #include <vector> #include <algorithm> using namespace std; int N, S, ans=0; int arr[21]; void func(int idx, int sum){ /* 모든 요소는 전부 순회해서 돌긴 해야 한다 --> 이렇게 안하면 S가 0일때 바로 종료된다. */ if(idx == N){ if(sum == S){ ans++; return; } } else{ /* 자신을 포함했거나, 포함안했거나 2가지 경우의수 수행 */ func(idx+1, sum); func(idx+1, sum+arr[idx]); } } int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> N >> S; for(int i=0;i<N;i++) cin >> arr[i]; func(0, 0); if(S == 0) ans--; cout << ans; return 0; }
- 주의할 점
1) 일단 모든 요소는 순회해야 한다
--> 그렇지 않으면 S가 0일때 경우 세지도 않고 바로 종료함
2)isused[]
불필요 !
isused[]
는 다시 돌아와서 사용의 여부에 따라 새로운 경우의 수를 돌게 하기 위해서 사용했음
하지만, 지금 문제는 그냥 자신을 포함하거나 포함하지 않거나 2가지 경우에 대해 재귀를 돌 뿐 돌아와서 새로운 경우의 수를 찾지는 않기에isused[]
가 필요하지 않다.
Author And Source
이 문제에 관하여(BOJ 1182 : 부분수열의 합 - C++), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@neity16/BOJ-1182-부분수열의-합-C저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)