📙[Algo] 24.07.30 알고리즘

알고리즘 문제) BOJ 10958. Ice Hockey World Championship

• 링크 : https://www.acmicpc.net/problem/10958

문제 요약

• 각 경기의 티켓 가격이 주어질때
• 예산을 초과하지 않고 경기를 관람할 수 있는 방법의 수는?
• 한 경기라도 다르게 관람하면 다른 케이스로 간주

시간 제한

• 1초

입력

• 두 개의 양의 정수 N과 M
  • 1 ≤ N ≤ 40, 1 ≤ M ≤ 10^18
  • 경기를 관람할 수 있는 경기 수와 예산
• N개의 양의 정수가 각각 공백을 두고 주어짐(각 경기의 비용)
  • 10^15이하

출력

• 경기를 관람할 수 있는 방법의 수
  • 최대 2^40가지

접근법

• N이 최대 40까지 가능하므로, 여기서 경기를 볼 수 있는 모든 케이스를 살핀다면 최악의 경우 2^40까지 가능해진다.
• 따라서 N을 2개의 그룹으로 나눈 뒤, 각 그룹별로 경기를 관람하는 가능한 조합들을 각각 리스트 A, B에 담아두고,
• A리스트 중심으로 순회하며, 각 케이스별로 B리스트에서 가능한 경우의 수를 뽑아낸다 ⇒ 이때 이분탐색 알고리즘을 사용
  • 가능한 경우의 최대 인덱스가 곧 가능한 경우의 개수
• 최종 시간 복잡도 : 2^(N/2+1) + (N/2)*log(N/2) ⇒ 2^21

코드

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

public class Main {
    static int N;
    static long M;
    static long[] arr;
    static ArrayList<Long> alst = new ArrayList<>();
    static ArrayList<Long> blst = new ArrayList<>();

    static void separate(int cur, int end, long sum) {
        if (sum > M) return;

        if (cur == end) {
            if (end == N / 2) alst.add(sum);
            else blst.add(sum);
            return;
        }

        separate(cur + 1, end, sum + arr[cur]);
        separate(cur + 1, end, sum);
    }

    static int binarySearch(long aNum) {
        int s = 0, e = blst.size() - 1, mid, ans = -1;
        long sum;
        while (s <= e) {
            mid = (s + e) / 2;
            sum = aNum + blst.get(mid);

            if (sum <= M) {
                ans = mid;
                s = mid + 1;
            } else {
                e = mid - 1;
            }
        }

        return ans;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Long.parseLong(st.nextToken());

        st = new StringTokenizer(br.readLine());
        arr = new long[N];
        for (int i = 0; i < N; i++) {
            arr[i] = Long.parseLong(st.nextToken());
        }

        separate(0, N / 2, 0);
        separate(N / 2, N, 0);

        Collections.sort(blst);

        long num, cnt = 0;
        int idx;
        for (int i = 0, size = alst.size(); i < size; i++) {
            num = alst.get(i);
            idx = binarySearch(num);

            if (idx != -1) {
                cnt += (idx + 1);
            }
        }

        System.out.println(cnt);
    }
}

 

알고리즘 문제) BOJ 6099. Exams

• 링크 : https://www.acmicpc.net/problem/6099

문제 요약

• N개의 시험이 존재
• 최소 T점을 달성할 수 있는 방법의 수는?

시간 제한

• 1초

입력

• 두개의 양의 정수 N과 T
  • N : 1 ~ 36
• N개의 양의 정수가 공백을 두고 주어짐
  • 각 시험의 정수를 의미하며 숫자는 10^13이하

출력

• T점을 달성할 수 있는 모든 경우의 수는?

접근법

• N이 36가지 가능하므로 백트랙킹으로 모든 경우를 탐색하면 2^36가지 ⇒ 최적화 필요
• 최적화를 위해 N개의 시험을 두 그룹으로 나눈다
  • 각 그룹별로 모든 조합 탐색 ⇒ 2 * 2^18
• a그룹 기준으로 원소 하나씩 순회하면서
  • b그룹에서 이분탐색알고리즘으로 시험점수합이 T점이상인 경우의 가장 최소 인덱스를 찾는다.
  • 이후 b그룹 사이즈 - 최소인덱스 + 1을 누적해서 정답 변수에 더해준다 ⇒ 모든 경우의 수
  • 여기서 시간복잡도는 18 * log18
• 최종 시간복잡도 ⇒ 2^19

코드

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

public class Main {
    static int N;
    static long T;
    static long[] arr;
    static ArrayList<Long> alst = new ArrayList<>();
    static ArrayList<Long> blst = new ArrayList<>();

    static void separate(int cur, int end, long sum) {
        if (cur == end) {
            if (end == N / 2) alst.add(sum);
            else blst.add(sum);
            return;
        }

        separate(cur + 1, end, sum + arr[cur]);
        separate(cur + 1, end, sum);
    }

    static int binarySearch(long aNum) {
        int s = 0, e = blst.size() - 1, mid, ans = -1;
        long sum;
        while (s <= e) {
            mid = (s + e) / 2;
            sum = aNum + blst.get(mid);

            if (T <= sum) {
                ans = mid;
                e = mid - 1;
            } else {
                s = mid + 1;
            }
        }
        return ans;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        T = Long.parseLong(st.nextToken());

        arr = new long[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Long.parseLong(st.nextToken());
        }

        separate(0, N / 2, 0);
        separate(N / 2, N, 0);
        Collections.sort(blst);

        int idx;
        long num, cnt = 0;
        for (int i = 0, size = alst.size(); i < size; i++) {
            num = alst.get(i);

            idx = binarySearch(num);
            if (idx != -1) {
                cnt += (blst.size() - idx);
            }
        }

        System.out.println(cnt);
    }
}