[백준/JAVA] 14225번: 부분수열의 합
🔺 문제
14225번: 부분수열의 합
수열 S가 주어졌을 때, 수열 S의 부분 수열의 합으로 나올 수 없는 가장 작은 자연수를 구하는 프로그램을 작성하시오. 예를 들어, S = [5, 1, 2]인 경우에 1, 2, 3(=1+2), 5, 6(=1+5), 7(=2+5), 8(=1+2+5)을 만들
www.acmicpc.net
🔺 코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
|
import java.util.*;
import java.io.*;
public class Main {
static int N;
static int[] arr;
static boolean[] visited = new boolean[20 * 1000000 + 1];
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
arr = new int[N];
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
for(int i = 0 ; i < N ; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
dfs(0, 0);
for(int i = 1 ; i < visited.length ; i++) {
if(!visited[i]) {
System.out.println(i);
break;
}
}
}
private static void dfs(int depth, int sum) {
if(depth == N) {
visited[sum] = true;
return;
}
dfs(depth + 1, sum + arr[depth]); // 🔔 수열 S에서의 원소를 합하는 경우
dfs(depth + 1, sum); // 🔔 수열 S에서의 원소를 합하지 않는 경우
}
}
|
cs |
✅ 해결 아이디어
✔ 브루트포스 + DFS
- 부분집합 합 구하기
└ DFS
└ 수열 S에서의 원소를 합하는 / 합하지 않는 경우 나눠서 재귀호출
💥 유의사항
• 수열에서 원소를 합하는 경우와 합하지 않는 경우를 분리해 구함
• 부분합 sum을 인자로 들고 가면서 업데이트 해주자
🔺 다른 풀이들
- 부분 수열의 합을 조합을 활용해서 푸심
백준 14225 부분수열의 합 (Java,자바)
이번에 풀어본 문제는 백준 14225번 부분수열의 합 입니다.
velog.io
- dfs문 안이 조금 다름
[백준] code.plus(브루트포스 - 재귀,JAVA)14225번, 부분수열의 합
문제 링크 14225번: 부분수열의 합 수열 S가 주어졌을 때, 수열 S의 부분 수열의 합으로 나올 수 없는 가장 작은 자연수를 구하는 프로그램을 작성하시오. 예를 들어, S = [5, 1, 2]인 경우에 1, 2, 3(=1+2)
tussle.tistory.com
💬 느낀 점
부분집합 원소의 합을 조합을 일일이 구해서 풀 생각을 했었는데...
자꾸 에러가 나서 다른 분들 풀이를 보고 작성했다...
코드가 생각보다 간단해서 당황..'
담에는 나도 이렇게 풀자!
| 1회독 | 2회독 | 3회독 | 4회독 | 5회독 |
| V |
(참고)
[JAVA] 백준 -부분 수열의 합 14225
onejunu.tistory.com
[백준] 14225 부분수열의 합 - JAVA
수열 S가 주어졌을 때, 수열 S의 부분 수열의 합으로 나올 수 없는 가장 작은 자연수를 구하는 프로그램을 작성하시오.예를 들어, S = 5, 1, 2인 경우에 1, 2, 3(=1+2), 5, 6(=1+5), 7(=2+5), 8(=1+2+5)을 만들 수
velog.io