[백준] 14225 부분수열의 합 - 브루트포스(재귀) JAVA

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

14225번: 부분수열의 합

코드설명

브루트포스인데 재귀를 활용해야만 시간초과를 벗어날 수 있는 문제입니다.

 

아래의 로직처럼

각 구간을 더하지않고 다음 단계로 넘어가고,

각 구간을 더하고 다음 단계로 넘어가는 로직

이 것을 구현해주면 됩니다.

 

또한 추가로 알아야할점은 부분수열이란 원래 수열의 순서를 유지한 수열을 부분수열이라고 합니다. (순서가 바뀌면 안된다는 의미입니다.)

 

 

 {1,2,3,4,5} 가 있다고 가정하면,

{0}, {1}, {1,2}, {1,3}, {1,4} {1,5}, {1, 2,3} ... 이런식으로 빠르게 해결할 수 있습니다.

재귀를 활용하여 사용한 코드 같은경우 각 순열에서 더하냐, 더하지 않냐의 2가지 방식으로만 진행되므로 불필요한 수열 연산이 더해지지 않으므로 시간초과가 걸리지 않는것입니다.

 

조금 더 코드적으로 생각해보면,

모든 경우가 더해지지 않는경우를 먼저 계산한뒤에 마지막 정수인 5 부터 더해지면서 진행될 것입니다.

{5} , {4,5} ... 이렇게 되겠습니다. 코드가 다 들어간뒤 + arr[level]으로 실행하기에 그렇습니다.

public static void simulate(int level, int sum) {
    if(level == N) {
        sumTemp[sum] = true;
        return ;
    }
 
    simulate(level + 1, sum);
    simulate(level+1, sum +arr[level]);
 
}

 

처음에 for문과 재귀를 함께 활용하여 진행해보았는데 아래와 같이 진행할경우 중복된 연산이 발생하였고, 

( 예로들면, 1 + 2 이 진행된 이후에 나중에 2 + 1 이 for문으로 인하여 다시 반복되는 경우가 있습니다. )

그리하여서 idx를 활용하여 앞에서 사용된 수열은 사용하지 않기에 idx를 처리하였더니 통과는 하지만, 훨씬 많은 연산이 필요하기에 시간과 메모리가 3~4배 이상 차이납니다.

    public static void simulate(int idx, int level, int sum) {
    	if(level > N) {
    		return ;
    	}
    	hashset.add(sum);
    	for(int i=idx; i<N;i++) {
    		if(visited[i] == false) {
    			visited[i] = true;
    			simulate(i+1, level+1, sum +arr[i]);
    			visited[i] = false;
    		}
    	}
    	
    }

 

단순하게 재귀를 활용하여 더하는 경우와 더하지 않는경우를 나누어서 재귀가 계속 실행되는 방식으로 하는것이 좋아보입니다.

 

 

코드

재귀를 활용하여 불필요한 연산, 메모리 사용하지않음

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
	
	public static int N;
	public static int answer = 0;
	public static int[] arr;
	public static boolean[] visited;
	public static boolean[] sumTemp = new boolean[20*100001];
    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());
    	arr = new int[N];
    	visited = new boolean[N];
    	st = new StringTokenizer(br.readLine());
    	for(int i=0;i<N;i++) {
    		arr[i] = Integer.parseInt(st.nextToken());
    	}
    	simulate(0, 0);
    	
    	for(int i=1; i<100000*20;i++) {
    		if(sumTemp[i] == false) {
    			System.out.println(i);
    			break;
    		}
    	}
    }
    
    public static void simulate(int level, int sum) {
    	if(level == N) {
        	sumTemp[sum] = true;
    		return ;
    	}
    	
    	simulate(level + 1, sum);
		simulate(level+1, sum +arr[level]);
    	
    }
    
    
}

 

 

hashset -> 배열 에다가 모든 순열을 구하면서 진행해본 코드 여전히 시간초과 ( 이코드는 idx사용안했서 중복연산하여 시간초과 발생)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
	
	public static int N;
	public static int answer = 0;
	public static int[] arr;
	public static boolean[] visited;
	public static boolean[] sumTemp = new boolean[20*100001];
    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());
    	arr = new int[N];
    	visited = new boolean[N];
    	st = new StringTokenizer(br.readLine());
    	for(int i=0;i<N;i++) {
    		arr[i] = Integer.parseInt(st.nextToken());
    	}
    	simulate(0, 0);
    	
    	for(int i=1; i<100000*20;i++) {
    		if(sumTemp[i] == false) {
    			System.out.println(i);
    			break;
    		}
    	}
    }
    
    public static void simulate(int level, int sum) {
    	if(level > N) {
    		return ;
    	}
    	sumTemp[sum] = true;
    	for(int i=0; i<N;i++) {
    		if(visited[i] == false) {
    			visited[i] = true;
    			simulate(level+1, sum +arr[i]);
    			visited[i] = false;
    		}
    	}
    	
    }
    
    
}

 

이후에 idx를 활용하여 중복되어 더해지는 값을 제거하여 solve

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.StringTokenizer;
 
public class Main {
	
	public static int N;
	public static int answer = 0;
	public static int[] arr;
	public static boolean[] visited;
	public static int[] answerArr;
	public static HashSet<Integer> hashset = new HashSet<Integer>();
    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());
    	arr = new int[N];
    	visited = new boolean[N];
    	st = new StringTokenizer(br.readLine());
    	for(int i=0;i<N;i++) {
    		arr[i] = Integer.parseInt(st.nextToken());
    	}
    	simulate(0, 0, 0);
    	
    	for(int i=1; i<100000*20;i++) {
    		if(!hashset.contains(i)) {
    			System.out.println(i);
    			break;
    		}
    	}
    }
    
    public static void simulate(int idx, int level, int sum) {
    	if(level > N) {
    		return ;
    	}
    	hashset.add(sum);
    	for(int i=idx; i<N;i++) {
    		if(visited[i] == false) {
    			visited[i] = true;
    			simulate(i+1, level+1, sum +arr[i]);
    			visited[i] = false;
    		}
    	}
    	
    }
    
    
}

 

 

처음에 시간초과가 난 코드 ( 이코드는 idx사용안했서 중복연산하여 시간초과 발생)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.StringTokenizer;
 
public class Main {
	
	public static int N;
	public static int answer = 0;
	public static int[] arr;
	public static boolean[] visited;
	public static int[] answerArr;
	public static HashSet<Integer> hashset = new HashSet<Integer>();
    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());
    	arr = new int[N];
    	visited = new boolean[N];
    	st = new StringTokenizer(br.readLine());
    	for(int i=0;i<N;i++) {
    		arr[i] = Integer.parseInt(st.nextToken());
    	}
    	simulate(0, 0);
    	
    	for(int i=1; i<100000*20;i++) {
    		if(!hashset.contains(i)) {
    			System.out.println(i);
    			break;
    		}
    	}
    }
    
    public static void simulate(int level, int sum) {
    	if(level > N) {
    		return ;
    	}
    	hashset.add(sum);
    	for(int i=0; i<N;i++) {
    		if(visited[i] == false) {
    			visited[i] = true;
    			simulate(level+1, sum +arr[i]);
    			visited[i] = false;
    		}
    	}
    	
    }
    
    
}