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