[백준/c++] 1182번: 부분수열의 합
🌱 문제
![]
🌱 풀이
- 부분수열의 갯수는 2^n-1개이다. (공집합 제외)
- for문은 1부터 2^n-1 까지 돌린다.
- k값은 현재 i의 이진수값의 인덱스에 해당하는 변수이다. 원소 갯수는 N개 이므로 N번 반복하면 되고, (1<<K)는 이진수 'i의 끝에서 K번째 수'가 1인지 0인지 확인하는 연산이다.
ex) 예를들어, i=15(1111), k=3이면 i 맨앞 자리(끝에서 0,1,2,3번째)수가 1인지 확인한다. i15&(1<<3) = 1 이므로 sum+=arr[3]; - 현재 값인 i와 (1<<k)의 AND연산을 통해 true일때만 arr[k]에 해당하는 수를 sum에 더하고, N번 다 돌면 sum이 s인지 확인한다.
- 각 i값과 (1<<k)
🌱 코드
//1182번: 부분수열의 합
/*
N,S
1 <= N <= 20
|S| <= 1,000,000
합이 s가 되는 부분수열의 갯수 출력
*/
#include <iostream>
#include <cmath>
using namespace std;
int n,s;
int arr[21];
int cnt;
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
cin>>n>>s;
int total= pow(2,n);
for(int i=0; i<n; i++){
cin>>arr[i];
}
for(int i=1; i<total ; i++){
int sum=0;
for(int k=0; k<n; k++){
if(i&(1<<k)){
sum+=arr[k];
}
}
if(sum==s){
// cout<<"i : "<<i<<"\n";
cnt++;
}
}
cout<<cnt<<"\n";
}
Author And Source
이 문제에 관하여([백준/c++] 1182번: 부분수열의 합), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@somyeong0623/백준c-1182번-부분수열의-합저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)