[백준] 14225번 : 부분수열의 합 - JAVA [자바]

https://www.acmicpc.net/problem/14225

14225번: 부분수열의 합

---

문제

 

 

아래 문제를 풀면서 부분집합을 비트마스킹으로 더 풀고 싶었고 부분집합 문제를 풀기위해 이 문제를 풀었다.

https://bean-conding.tistory.com/12

[백준] 15661번 : 링크와 스타트 - JAVA [자바]

 

내가 생각한 로직은

1. 부분집합을 구한다.

2. 부분집합들의 합을 구하고 리스트에 저장한다.

3. 저장된 리스트를 오름차순 정렬한다.

4. 결과값을 0으로 셋팅하고 +1 값이 리스트의 0인덱스부터 같은지 안같은지 검사한다.

• 만약 +1 한 값이 리스트의 인덱스 값과 일치하다면 결과값을 +1 해준다.
• 만약 결과값과 리스트의 인덱스 값과 일치하지 않다면 for 문을 중지한다.

 

아래는 비트마스킹을 이용한 부분집합 구하는 메서드이다.

// 비트마스킹으로 부분집합 구하는 메서드 
static void bitSubSet() {
	for(int i = 0; i < 1 << N; i++) {
		int sum = 0;
		
		for(int j = 0; j < N; j++) {
			if((1 & i >> j) == 0) continue;
			
			System.out.print(j + " ");
		}
		System.out.println();
	}
}

 

 

위 코드를 실행하면 위 사진과 같이 부분집합이 구해지는 것을 알 수 있다.

 

1번 로직은 끝나고 이제 2,3,4번 로직은 단순 구현 해주면 끝이다.

 

어떻게 비트마스킹으로 부분집합을 구현할 수 있는지는 다음 블로그가 잘 설명해준다.

https://selina-park.tistory.com/103

[알고리즘_개념] 비트마스크 연산, 부분집합의 표현

---

전체 코드

public class Main {
	static int N;
	static String S;
	static int[] arr;
	static List<Integer> list;
	
	public static void main(String[] args) throws Exception {
    	System.setIn(new FileInputStream("input.txt"));
    	BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    	StringBuilder sb = new StringBuilder();
    	StringTokenizer st;
    	
    	N = Integer.parseInt(in.readLine());
    	S = in.readLine();
    	st = new StringTokenizer(S);
    	arr = new int[N];
    	list = new ArrayList<>();
    	
    	for(int i = 0; i < N; i++) {
    		arr[i] = Integer.parseInt(st.nextToken());
    	}
    	
    	bitSubSet();
        
        // 3. 리스트를 오름차순 정렬후.
    	Collections.sort(list);
 
    	int result = 0;
    	
        // 4번 로직. 
    	for(int i = 0; i < list.size(); i++) {
    		int num = list.get(i);
    		
    		if(result + 1 == num) {
    			result++;
    		}
    		else if(result != num) {
    			break;
    		}
    	}
    	
    	System.out.println(result + 1);
    }
	
	// 비트마스킹으로 부분집합 구하는 메서드. 
	static void bitSubSet() {
		for(int i = 0; i < 1 << N; i++) {
			int sum = 0;
			
			for(int j = 0; j < N; j++) {
				if((1 & i >> j) == 0) continue;
				
                // 2번 로직 부분집합의 합을 구한다. 
				sum += arr[j];
			}
			
			if(sum == 0) continue;
			
            // 합을 리스트에 저장. 
			list.add(sum);
		}
	}
}

 

---

결과