PS/BOJ
1182(조합 비교)
easy16
2022. 5. 3. 17:07
부분수열의 합 : https://www.acmicpc.net/problem/1182
숏코드 : https://www.acmicpc.net/source/11440468
S=0 일때, 아무런 인자없이 count하는 경우를 조심
제출에는 빠졌지만, 실수 방지 및 디버그를 위해 로그를 항상 출력하며 확인할 것.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
/*
5 0
-7 -3 -2 5 8
*/
public class Main {
static int N, S;
static int[] arr, combi;
static int answer;
private static boolean DBG = false;
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());
arr = new int[N];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
dfs(0, 0, 0);
System.out.println(answer);
}
private static void dfs(int index, int start, int sum) {
/*don't count empty case*/
if (index > 0 && sum == S)
answer++;
for (int i = start; i < N; i++) {
dfs(index + 1, i + 1, sum + arr[i]);
}
}
}
숏코드 방식
import java.util.*;
public class Main {
static int ans=0;
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int s=sc.nextInt();
int a[]=new int[n];
for(int i=0;i<n;i++) {
a[i]=sc.nextInt();
}
if(s==0) {
ans=-1;
}
go(a,0 ,s,0, "");
System.out.println(ans);
}
static void go(int a[],int index,int s,int num, String str ) {
if(index==a.length) {
System.out.println(str);
if(num==s)
ans++;
return;
}
go(a,index+1,s,num+a[index],str+" " + a[index]);
go(a,index+1,s,num,str);
}
}
출력 비교
ex)
3 0
1 2 3
기존 :
1
1 2
1 2 3
1 3
2
2 3
3
숏코드:
1 2 3
1 2
1 3
1
2 3
2
3