728x90
1182 - 부분수열의 합
https://www.acmicpc.net/problem/1182

문제
N개의 정수로 이뤄진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수
입력
첫째 줄: 정수의 개수 N, 정수 S (1 <= N <= 20, |S| <= 1,000,000)
둘째 줄: N개의 정수 (|주어지는 정수| <= 100,000)
출력: 합이 S가 되는 부분수열의 개수
풀이
비트
- `1 << N`: 숫자 N개 중 일부를 골라 합이 S가 되는 경우의 수
-> 부분집합 개수: 2^N개 -> 0 ~ (2^N - 1) - `(mask & (1 << i)) != 0`: mask의 i번째 비트가 켜져 있으면 `nums[i]`를 포함
- mask: 부분집합 선택 정보 저장한 숫자 / 비트 하나: 해당 원소 선택했는지 여부
- ex. mask = 5 = 101 / 1 << i에서 i가 2라면 1 << 2 = 100
-> mask & (1 << 2) = 100 - AND 연산 규칙: 두 비트 모두 1일 때만 1
-> i번째 비트가 1이면 true = i번째 원소를 포함한다는 의미
int cnt = 0;
for (int mask = 1; mask < (1 << N); mask++) {
int sum = 0;
for (int i = 0; i < N; i++) {
if ((mask & (1 << i)) != 0) sum += nums[i];
}
if (sum == S) cnt++;
}
코드
비트
import java.io.*;
import java.util.*;
public class boj_1182 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int S = Integer.parseInt(st.nextToken());
int[] nums = new int[N];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
nums[i] = Integer.parseInt(st.nextToken());
}
int cnt = 0;
for (int mask = 1; mask < (1 << N); mask++) {
int sum = 0;
for (int i = 0; i < N; i++) {
if ((mask & (1 << i)) != 0) sum += nums[i];
}
if (sum == S) cnt++;
}
System.out.println(cnt);
}
}
DFS
import java.io.*;
import java.util.*;
public class boj_1182 {
static int N, S;
static int[] nums;
static int cnt = 0;
public static void dfs(int depth, int sum) {
if (depth == N) {
if (sum == S) cnt++;
return;
}
dfs(depth + 1, sum + nums[depth]);
dfs(depth + 1, sum);
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
S = Integer.parseInt(st.nextToken());
nums = new int[N];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) nums[i] = Integer.parseInt(st.nextToken());
dfs(0, 0);
if (S == 0) cnt--;
System.out.println(cnt);
}
}
728x90
반응형
'✏️ > BOJ' 카테고리의 다른 글
| [BOJ/Two Pointers] 백준 1253 - 좋다 (Java) (0) | 2026.02.22 |
|---|---|
| [BOJ/비트] 백준 11723 - 집합 (Java) (0) | 2026.02.16 |
| [BOJ/Segment Tree] 백준 2268 - 수들의 합 7 (Java) (0) | 2026.02.16 |
| [BOJ/Merge Sort] 백준 1517 - 버블 소트 (Java) (0) | 2026.01.15 |
| [BOJ/DFS] 백준 3109 - 빵집 (Java) (0) | 2026.01.13 |