23.01.12 TIL 백준 14225 문제 (Java)

오늘 한 일

• 백준 3문제 풀기
• Spring 강의 듣기 

공부하면서 궁금한 점

부분수열의 합

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

512 MB

8926

4242

2883

43.530%

문제

수열 S가 주어졌을 때, 수열 S의 부분 수열의 합으로 나올 수 없는 가장 작은 자연수를 구하는 프로그램을 작성하시오.

예를 들어, S = [5, 1, 2]인 경우에 1, 2, 3(=1+2), 5, 6(=1+5), 7(=2+5), 8(=1+2+5)을 만들 수 있다. 하지만, 4는 만들 수 없기 때문에 정답은 4이다.

입력

첫째 줄에 수열 S의 크기 N이 주어진다. (1 ≤ N ≤ 20)

둘째 줄에는 수열 S가 주어진다. S를 이루고있는 수는 100,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 수열 S의 부분 수열의 합으로 나올 수 없는 가장 작은 자연수를 출력한다.

예제 입력 1 

3
5 1 2

예제 출력 1 

4

 

완전탐색 문제를 계속 풀다보니 어느정도 익숙해진 느낌이다.

생각보다 쉽게 풀렸다.

수열의 크기가 최대 20, 수의 최대 값은 20만 이므로 다 돈다해도 최악의 경우 200만이 나온다.

거기에 수열을 합해서 나올수 있는 경우의 수 2^20 정도 이므로 100만 정도를 더한다해도 300만으로 2초는 충분하다.

 

풀이를 보자면

1. 수열들의 합이 될 수 있는 경우의 수를 구해 Set에 넣는다. ->  하지 않아도 상관 없지만 중복 제거를 위해 

2. 나올 수 있는 최소값 1부터 최악의 경우인 200만까지 차례대로 돌며 그 값이 경우의 수에 없으면 최솟값이므로 출력한다.

public class 백준14225 {
    static int[] sequence;
    static int n;
    static Set<Integer> setSumNum = new HashSet<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        n = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine(), " ");
        sequence = new int[n];
        for(int i = 0; i < n; i++){
            sequence[i] = Integer.parseInt(st.nextToken());
        }

        sumFind(0, 0);
        System.out.println(minFind());
    }
    public static int minFind(){
        int result = 0;
        for(int i = 1; i<= 2000000; i++){
            if(setSumNum.contains(i)){
                continue;
            }
            result = i;
            break;
        }
        return result;
    }

    public static void sumFind(int depth, int sum){
        if(depth == n){
           if(sum>0)
            setSumNum.add(sum);
           return;
        }
        sumFind(depth +1, sum + sequence[depth]);
        sumFind(depth +1, sum);
    }
}

 

53962629

dbsgud101

14225

맞았습니다!!

66640

544

Java 11 / 수정

1283

시간이 오래 나와 다른 사람들의 코드를 살펴보니

최소값을 찾을 때 set을 사용하지 않고 boolean배열을 200만으로 만들어 true일 경우 통과 false일경우

출력하는 식으로 한것을 볼 수있었다.

 

다양한 코드를 보며 더욱 익숙해 져야겠다. 

---

 내일 할 일

• 백준 3문제 풀기
• 자바 강의 듣기