[백준] 14225번 부분수열의 합 재귀로 풀어보기
1. 문제
1) 링크
2) 문제
수열 S가 주어졌을 때, 수열 S의 부분 수열의 합으로 나올 수 없는 가장 작은 자연수를 구하는 프로그램을 작성하시오.
예를 들어, S = [5, 1, 2]인 경우에 1, 2, 3(=1+2), 5, 6(=1+5), 7(=2+5), 8(=1+2+5)을 만들 수 있다. 하지만, 4는 만들 수 없기 때문에 정답은 4이다.
3) 입력
첫째 줄에 수열 S의 크기 N이 주어진다. (1 ≤ N ≤ 20)
둘째 줄에는 수열 S가 주어진다. S를 이루고있는 수는 100,000보다 작거나 같은 자연수이다.
4) 출력
첫째 줄에 수열 S의 부분 수열의 합으로 나올 수 없는 가장 작은 자연수를 출력한다.
더 자세한 문제의 제한과 예시를 보려면 위의 링크를 클릭해서 확인해보자
2. 풀이
이 문제는 재귀를 사용하여서 부분 수열의 합으로 표현해보는 문제이다. 꼭 재귀를 사용하지 않아도 된다! 다른 방법은 시간이 나면 또 포스팅을 해보도록 하겠다.
우선 이 문제는 각각의 index마다 사용할지, 사용하지 않을지를 결정하면서 재귀함수를 돌리면 된다.
언제나 그렇듯, 나는 algo(int index, int sum) 이라는 함수를 준비했다.
그리고 중요한 것은 이번에는 합이 나올수 있는지 없는지를 체크하는 것이 중요한 것이어서
HashSet을 준비했다. 겹치는 것은 신경쓰지 않기 위함이다.
ArrayList를 사용하여도 정확도에는 지장이 없다.
algo(int index, int sum) 함수의 종착지는
index가 n (전체 수의 개수) 와 같아지는 순간이고 그때마다 HashSet에 sum을 추가해주면 된다.
만약 n과 같아지지 않는다면
1. 해당 index를 사용할 경우 : algo(index+1, sum+a[i])
2. 해당 index를 사용하지 않을 경우: algo(index+1, sum)
이렇게 두개로 나누어서 풀면 된다.
이를 코드화한 algo 함수의 부분코드는 아래와 같다.
static HashSet<Integer> hs=new HashSet<>();
public static void algo(int index, int sum){
if (index==n){
hs.add(sum);
return;
}
algo(index+1, sum+a[index]);
algo(index+1, sum);
}그리고 문제에서 1부터 나오지 않은 수를 찾아달라고 했으므로 1부터 하나씩 수를 증가시키면서 HashSet에 해당수가 있는지의 여부를 판단해주면 된다.
3. 코드
이를 적용한 전체 코드는 아래와 같다.
import java.util.*;
public class Main{
static HashSet<Integer> hs=new HashSet<>();
static int a[];
static int n;
public static void algo(int index, int sum){
if (index==n){
hs.add(sum);
return;
}
algo(index+1, sum+a[index]);
algo(index+1, sum);
}
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
n=sc.nextInt();
a=new int[n];
for(int i=0; i<n; i++){
a[i]=sc.nextInt();
}
algo(0,0);
Arrays.sort(a);
int current=1;
int ans=0;
while(true){
if (!hs.contains(current)){
ans=current;
break;
}
current++;
}
System.out.println(ans);
}
}
물론 여기서 재귀를 사용하면 숫자를 아무것도 사용하지 않아서 sum이 0이 나오는 것이 존재하고 틀림없기 그것이 HashSet에 들어가 있을 것이다. 하지만 문제에서 자연수부터라고 했기 때문에 이 부분은 신경쓰지 않고 구해주면 된다.