[붕어빵 꼬리먼저 팀] 1회차 - 학습 마무리

2021/01/05 동계 모각코 1회차

 

오늘 학습하고자 했던 분야인 Two pointer와 Meet in the middle에 대한 문제를 각각 하나씩 골라서 풀이하려 했습니다.

생소한 내용을 바로 코딩하다보니 모각코 활동 시간으로는 부족하여 Meet in the middle에 대한 문제는 풀이하지 못했습니다.

풀이한 부분까지 코드로 올리겠습니다.

 

---

[Two pointer] www.acmicpc.net/problem/1644

에라토스테네스의 체를 응용한 두 포인터 문제입니다.

 

배열의 연속합 중 특정값 S와 같아지는 경우의 수를 구하는 문제입니다.

그러나 일반적인 배열이 아닌 소수로만 이루어진 배열입니다.

 

N의 범위가 작으므로 에라토스테네스의 체를 사용하여 소수의 리스트를 구한 뒤, 해당 리스트에 두 포인터를 적용시켜서 경우의 수를 구하였습니다.

누적합을 사용하여 현재까지의 sum을 빠르게 구하는 방법이 있으나, 포인터가 이동함에 따라 현재까지 구한 sum에서 빼고 더하는 방법으로 풀이하였습니다.

1에 대해 런타임 에러가 발생하여 예외처리를 하였습니다.

 

 

[소스 코드]

 

import java.io.*;
import java.util.*;

public class Main {
    private static boolean[] isPrime;
    private static ArrayList<Integer> prime;

	public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        init(N);
        System.out.println(twoPointer(N));
    }

    private static int twoPointer(int N) {
        if (N == 1) return 0;
        int result = 0, size = prime.size();
        int left = 0, right = 0;
        int cur = prime.get(left);

        while (left < size) {
            if (right != size - 1 && cur < N) {
                cur += prime.get(++right);
            } else {
                if (cur == N) result++;
                else if (cur < N) break;
                cur -= prime.get(left++);
            }
        }

        return result;
    }

    private static void init(int N) {
        isPrime = new boolean[N + 1];
        prime = new ArrayList<Integer>();

        for (int i = 2; i < N + 1; i++) {
            if (isPrime[i] == false) {
                prime.add(i);
                for (int j = i; j < N + 1; j += i) {
                    isPrime[j] = true;
                }
            }
        }
    }
}

 

---

 

[Meet in the middle] www.acmicpc.net/problem/1450

기본적인 중간에서 만나기 문제입니다.

 

N개의 원소의 부분수열에서 S보다 작은 모든 경우의 수를 체크하는 문제입니다.

 

N의 제한이 30이고 모든 부분수열을 구하는 시간 복잡도가 $O(2^N)$이므로 당연히 시간초과에 걸리게 됩니다.

그런데 N의 제한이 애매하게 높으므로 N을 반으로 쪼개서 두 부분수열을 구한 뒤에 두 부분수열에 대하여 이분 탐색을 통한 upper bound를 구하여 S보다 작은 경우의 수를 확인한다면 시간 안에 들어올 수 있습니다.

 

또한 해당 문제에서는 아무런 원소를 고르지 않는 것도 경우의 수로 포함시키므로 공집합에 대한 예외처리를 할 필요가 없어집니다.

그리고 모든 무게가 1, 무게 제한이 $10^9$인 경우처럼 모든 경우를 다 세도 N의 최대 제한이 30이므로 2^30에 불과하여 int형으로 결과를 출력해도 정상적으로 출력이 가능합니다.

 

 

[소스 코드] 미완성

 

import java.io.*;
import java.util.*;

public class Main {
    private static int N, S;
    private static int[] arr1, arr2;
    private static ArrayList<Integer> list1, list2;

	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());
        int r, l;
        r = N / 2; l = N - r;

        init(l, r);

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

        setList1(0, 0, l); setList2(0, 0, r);
        Collections.sort(list1); Collections.sort(list2);

        br.close();
    }

    // binarySearch함수 필요

    private static void setList1(int sum, int depth, int l) {
        if (sum > S) return;
        if (depth == l) {
            list1.add(sum);
            return;
        }
        setList1(sum + arr1[depth], depth + 1, l);
        setList1(sum, depth + 1, l);
    }

    private static void setList2(int sum, int depth, int r) {
        if (sum > S) return;
        if (depth == r) {
            list2.add(sum);
            return;
        }
        setList1(sum + arr1[depth], depth + 1, r);
        setList1(sum, depth + 1, r);
    }

    private static void init(int l, int r) {
        arr1 = new int[l]; arr2 = new int[r];
        list1 = new ArrayList<>(); list2 = new ArrayList<>();
    }
}