문제 URL : https://www.acmicpc.net/problem/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
문제 접근법 : dfs를 이용하여 최소 1개에서 최대 n개까지 더하는 수를 구하여 나올수있는 수를 visit 처리하였고
동일한수를 더하지 않기위해 vector안에 있는 index또한 visit처리하여 dfs를 이용하여 1부터 무한대까지
나올수 없는 수를 찾아 그것을 출력하고 프로그램 종료시키면 되는 문제입니다.
소스코드 :
|
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
42
43
44
45
|
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int n;
int visit[2000001];
int visit2[20];
vector<int>v;
void dfs(int cnt,int idx,int sum){
if (cnt >= n){
return;
}
for (int i = idx; i < n; i++)
{
int nextsum = v[i] + sum;
if (visit2[i] == 0){
visit[nextsum] = 1;
visit2[i] = 1;
dfs(cnt + 1, i, nextsum);
visit2[i] = 0;
}
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n;
v.resize(n);
for (int i = 0; i < n; i++){
cin >> v[i];
}
dfs(0, 0, 0);
for (int i = 1;; i++){
if (visit[i] == false)
{
cout << i << "\n";
return 0;
}
}
}
|
cs |
'백준' 카테고리의 다른 글
| 백준 17088 등차수열 변환 (0) | 2020.08.05 |
|---|---|
| 백준 16197 두 동전 (0) | 2020.07.31 |
| 백준 16948 데스 나이트 (0) | 2020.07.31 |
| 백준 1463 1로 만들기 (0) | 2020.07.27 |
| 백준 10825 국영수 (0) | 2020.07.27 |