[JAVA] 백준 -부분 수열의 합 14225

www.acmicpc.net/problem/14225

14225번: 부분수열의 합

 

 

부분 수열이 처음엔 연속된 수의 나열인 줄 알고 풀었다가 아니였다.

 

원래 수열이  [1,4,3,2,3,1]  와 같이 있다면 [1], [1,3,2],[1,4,3],... 처럼 1개 이상의 원래의 순서를 유지한 수열을 부분 수열이라고 한다.

 

이러한 정의를 문제에 알려주면 좋았다만.. 여튼 문제는 어렵지 않으나 문제는 방문 체크이다.

 

방문 체크를 Set으로 해놓은 것과 boolean으로 미리 최대의 수만큼 선언해놓고 하는 것과 차이가 생각보다 엄청 크다는 것이다.

 

방문 체크를 Set으로 한 코드이다.

import java.util.*;

class Main{
    static int n;
    static int[] arr;
    static Set<Integer> set = new HashSet<>();
    static int answer = 1;
    
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        arr = new int[n];
        for(int i=0;i<n;i++) arr[i] = sc.nextInt();
        dfs(0,0);
        while(true){
            if(set.contains(answer))
            {
                answer++;
            }
            else{
                break;
            }
        }
        System.out.println(answer);
    }

    static void dfs(int idx,int sum){
        if(idx == n){
            if(sum>0)
            set.add(sum);
        }
        else{
            dfs(idx+1,sum+arr[idx]);
            dfs(idx+1,sum);
        }
    }

}

 

그다음 boolean으로 한 코드다.

 

import java.util.*;

class Main{
    static int n;
    static int[] arr;
    static boolean[] visited = new boolean[20*100000 + 10];
    static int answer = 1;

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        arr = new int[n];
        for(int i=0;i<n;i++) arr[i] = sc.nextInt();
        dfs(0,0);
        while(visited[answer]){
            answer++;
        }
        System.out.println(answer);
    }

    static void dfs(int idx,int sum){
        if(idx == n){
            visited[sum] = true;
        }
        else{
            dfs(idx+1,sum+arr[idx]);
            dfs(idx+1,sum);
        }
    }

}

 

속도 차이는 다음과 같다.

 

 

메모리도 많이 차이난다. 여기서 알수있는 점은 Set으로 방문체크 하다가 몇 배는 더 느려질 수 있다는 점이다.