📙[Algo] 24.02.05 알고리즘

알고리즘 문제) BOJ 23032. 서프라이즈~

23032번: 서프라이즈~

문제 요약

• N명의 학생 1~N번 학번
• 먹고 싶은 스테이크 그램 조사
• 다음 조건에 따라 이벤트 진행
  • 임의로 연속된 학번의 학생들 선택
  • 임의로 대상 학생들을 두 그룹으로 나눔
    • 그룹별로 학번이 인접해야 하며, 최소 1명 이상으로 구성
  • 두 그룹의 무게 합 차 E 구하기(큰 - 작)
  • E가 최솟값인 두 그룹이 당첨
    • 여러 개가 있다면 스테이크 무게 합이 가장 큰 두 그룹 당첨

시간 제한

• 1초

입력

• N
  • 2~2000
• 1번부터 N번 학생까지 적은 스테이크 무게 W
  • 1≤W≤10000

출력

• 이벤트에 당첨된 학생들의 스테이크 무게 합 출력

접근법

• 완전 탐색으로 접근하기
  • 2명 이상 N명까지 선택하는 모든 경우의 수를 구함
    그리고 그 안에서 임의로 두 그룹으로 나눌 수 있는 모든 경우의 수 구하면서 E최솟값으로 갱신
    (동점이 있다면 무게합이 더 큰 걸로 저장)
  • for i=0~N-2 : 대상 시작 지점 선택
    • for j=i+1~N-1 : 대상 끝 지점 선택
      • for k=i~j-1 : 그룹을 나눌 기준점 선택 [i~k, k+1~j]
      • ⇒ 2000*2000*2000 = 80억 최대 2중 for문 까지만 가능하다.
• 최적화 진행
  • 일단 대상 시작 지점과 끝 지점 정하는 곳까지는 2중 for문을 사용해도 된다.
    기준점 선택에 이진탐색을 적용해본다.  
    • 5 10 5 3 20 11  
    • s=0, e=5, mid=2
      • 두 그룹의 무게는 20, 34
      • 무게차는 14
      • 오른쪽 그룹이 더 크므로 s=mid+1
    • s=3, e=5, mid=4
      • 두 그룹의 무게는 43, 11
      • 무게차는 32
      • 왼쪽 그룹이 더 크므로 e=mid-1
    • s=3, e=4, mid=3
      • 두 그룹의 무게는 23, 31
      • 무게차는 8
      • 오른쪽 그룹이 더 크므로 s=mid+1
    • s=4, e=4, mid=4
      • … 여기까지하고 중단
  • ⇒ 중간 인덱스를 기준으로 우선적으로 무게합을 비교하고, 만약 왼쪽 그룹이 크다는 것은 인덱스 후보로 현재 인덱스 보다 우측은 아예 제외 대상이다(무게를 더 늘리면 안되니까)
    ⇒ 즉 왼쪽 그룹이 크면 인덱스를 좌측으로 떙겨야 하니까 e=mid-1, 오른쪽 그룹이 크면 인덱스를 우측으로 땡겨야 하니까 s=mid+1
    ⇒ 합계는 누적합으로 최적화 진행(무작정 돌리지 말고 신중하게 최적화 할 수 있는 부분 찾아보자…!), 누가봐도 합계 부분에 시간초과 뜰 수밖에 없었는데 무작정 돌렸었당,,,;;; 지금까지 배운거 자꾸 까먹지 말고 적극 활용하는 연습 합시다!

코드

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


public class Main {
    static int N;
    static int[] grams;
    static int answer = Integer.MAX_VALUE;
    static int ansGram = 0;

    static int binarySearch(int s, int e, int[] arr) {

        int start = s, end = e;
        int mid, group1, group2, diff;
        while (s <= e) {
            mid = (s + e) / 2;

            group1 = grams[mid] - grams[start - 1];
            group2 = grams[end] - grams[mid];

            if(group1 > group2){
                e = mid - 1;
            } else{
                s = mid + 1;
            }

            diff = Math.abs(group1 - group2);

            if (answer > diff) {
                answer = diff;
                ansGram = group1 + group2;
            } else if (answer == diff) {
                if (ansGram < group1 + group2) {
                    ansGram = group1 + group2;
                }
            }
        }

        return answer;
    }

    public static void main(String[] args) throws  IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        N = Integer.parseInt(br.readLine());

        StringTokenizer st = new StringTokenizer(br.readLine());
        grams = new int[N + 1];
        for (int i = 1; i <= N; i++) {
            grams[i] = grams[i - 1] + Integer.parseInt(st.nextToken());
        }

        // 대상 그룹 시작 인덱스 선택
        for (int i = 1; i <= N - 1; i++) {
            // 대상 그룹 끝 인덱스 선택(2명이상 N명이하)
            for (int j = i+1; j <= N; j++) {
                binarySearch(i, j, grams);
            }
        }

        bw.write(String.valueOf(ansGram));
        bw.flush();
        bw.close();
        br.close();
    }
}

 

알고리즘 문제) BOJ 13423. Three Dots

13423번: Three Dots

문제 요약

• 직선 위에 서로 다른 N개의 점
• 점 i 위치는 xi
• N개의 점 중 3개를 골라 가장 왼쪽에 있는점은 a, 가운데는 b, 가장 오른쪽은 c라고 할 때
• 세점의 간격이 같다 Xb-Xa = Xc-Xb
• 간격이 같은 세점이 가능한 경우 몇 가지?

시간 제한

• 1초

입력

• 테스트 케이스 T
• 각각의 테스트 케이스
  • 점의 개수 N (3≤N≤1,000)
  • N개의 점의 위치 X1,X2, … ,Xn
    • 모든 점의 위치는 -1억~1억

출력

• 세 점의 간격이 같은 경우 몇 가지인지 출력

접근법

• 완전 탐색으로 생각하기
  • 3중 for문을 사용해서 세 개의 모든 점을 방문하며 간격이 같은 경우만 카운팅 한다.
• 최적화하기 
  • 점의 개수가 1000개까지 주어질 수 있기 때문에, 최대 2중 for문만 가능하다.
    -4 -1 0 2 4
    1. 2중 for문을 사용해서 점 두 개를 찍는다.(A,B)
    2. 두 점 사이의 거리를 구한다(dist).
    3. 다른 한 점(C)는 B + dist여야 한다.
    ⇒ 이분 탐색으로 해당 값이 존재하는지 찾기(s = B의 인덱스, e = N - 1)

코드

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


public class Main {
    static int T, N;
    static int[] arr;
    static int dist;
    static int answer;

    static void binarySearch(int s, int e, int key) {
        int mid;
        while (s <= e) {
            mid = (s + e) / 2;

            if (arr[mid] < key) {
                s = mid + 1;
            } else if (arr[mid] > key) {
                e = mid - 1;
            } else {
                answer++;
                return;
            }
        }

    }

    public static void main(String[] args) throws  IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();

        T = Integer.parseInt(br.readLine());

        StringTokenizer st;
        while (T-- > 0) {
            N = Integer.parseInt(br.readLine());

            st = new StringTokenizer(br.readLine());

            arr = new int[N];
            for (int i = 0; i < N; i++) {
                arr[i] = Integer.parseInt(st.nextToken());
            }
            Arrays.sort(arr);

            answer = 0;
            for (int i = 0; i < N; i++) {
                for (int j = i + 1; j < N; j++) {
                    dist = arr[j] - arr[i];
                    binarySearch(j, N - 1, arr[j] + dist);
                }
            }

            sb.append(answer+"\n");
        }





        bw.write(String.valueOf(sb));
        bw.flush();
        bw.close();
        br.close();
    }
}

 

알고리즘 문제) BOJ 1654. 랜선 자르기

1654번: 랜선 자르기

문제 요약

• K개의 랜선을 갖고 있음
• K개의 랜선으로 N개의 같은 길이의 랜선으로 만들려고 함
  • N개보다 많이 만들어도 된다.
• 이때 만들 수 있는 최대 랜선의 길이는?

시간 제한

• 2초

입력

• 랜선의 개수 K, 필요한 랜선의 개수 N
  • 1≤K≤10,000
  • 1≤N≤1,000,000
  • K≤N
• K개 줄에 랜선의 길이가 주어짐
  • 2^31-1보다 작거나 같은 자연수

출력

• N개를 만들 수 있는 랜선의 최대 길이를 센티미터 단위의 정수로 출력

접근법

• 완전 탐색으로 생각하기
  길이 1~최대 랜선 길이까지 잘라보면서 N개를 만들 수 있는 지 체크한다.
  그러나 랜선 길이가 2^31-1까지 주어지므로 모든 길이를 탐색하면 안 된다.
• 최적화 하기
  1~최댓값 사이의 중간 길이부터 탐색한다.
  만약 해당 길이로 N개 이상의 랜선을 만들 수 있다면 길이를 좀더 늘리기 위해 s=mid+1, 아니라면 길이를 줄여야 하므로 e=mid-1로 진행.

코드

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


public class Main {
    static int K, N;
    static int max = 0;
    static int[] arr;
    static long answer = 0;

    static void binarySearch(long s, long e) {
        long mid;
        int cnt;
        while (s <= e) {
            mid = (s + e) / 2;

            cnt = 0;
            for (int i = 0; i < K; i++) {
                cnt += arr[i] / (int)mid;
            }

            if (cnt >= N) {
                answer = Math.max(answer, mid);
                s = mid + 1;
            } else {
                e = mid - 1;
            }
        }
    }

    public static void main(String[] args) throws  IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        K = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());

        arr = new int[K];
        for (int i = 0; i < K; i++) {
            arr[i] = Integer.parseInt(br.readLine());
            max = Math.max(max, arr[i]);
        }

        binarySearch(1, max);


        bw.write(String.valueOf(answer));
        bw.flush();
        bw.close();
        br.close();
    }
}

 

알고리즘 문제) BOJ 28449. 누가 이길까

28449번: 누가 이길까

문제 요약

• HI팀 N명, ARC팀 M명
• 서로 모든 사람끼리 한 번 씩 대결 ⇒ N*M
• 실력이 높은 참가자가 승리, 같다면 무승부
• 결과 예측

시간 제한

• 1초

입력

• HI팀 인원수 N, ARC팀 인원수 M
  • 1≤N,M≤10만
• HI팀의 코딩실력 ai가 N개 주어짐
  • 1≤ai≤10만
• ARC팀의 코딩실력 bi가 M개 주어짐
  • 1≤bi≤10만

출력

• HI팀 참가자의 승리 횟수, ARC팀 참가자 승리횟수, 무승부 횟수 출력

접근법

• 완전 탐색으로 점근하기
  • 2중 for문으로 모든 경우의수 탐색 ⇒ 10만 * 10만으로 시간초과
• 최적화 하기
  • 오름차순 정렬
  • lowerBound ⇒ 나보다 크거나 같은 애들 중 가장 왼쪽 인덱스 찾기
  • upperBound ⇒ 나보다 큰 애들중 가장 왼쪽 인덱스 찾기

코드

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


public class Main {
    static int N, M;
    static int[] hi;
    static int[] arc;

    // 나보다 크거나 같은 것들 중 가장 왼쪽 인덱스
    static int lowerBound(int s, int e, int key) {
        int answer = M;
        int mid;
        while (s <= e) {
            mid = (s + e) / 2;

            if (arc[mid] >= key) {
                answer = mid;
                e = mid - 1;
            } else{
                s = mid + 1;
            }
        }
        return answer;
    }

    static int upperBound(int s, int e, int key) {
        int answer = M;
        int mid;
        while (s <= e) {
            mid = (s + e) / 2;

            if (arc[mid] > key) {
                answer = mid;
                e = mid - 1;
            } else {
                s = mid + 1;
            }
        }
        return answer;
    }

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

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

        hi = new int[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            hi[i] = Integer.parseInt(st.nextToken());
        }

        arc = new int[M];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < M; i++) {
            arc[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(hi);
        Arrays.sort(arc);

        long same = 0, hiWin = 0, arcWin = 0;
        int lb, ub;
        for (int i = 0; i < N; i++) {
            // hi기준 탐색

            // 나보다 크거나 같은 애들 중 가장 왼쪽
            lb = lowerBound(0, M - 1, hi[i]);
            // 나보다 큰 애들 중 가장 왼쪽
            ub = upperBound(0, M - 1, hi[i]);

            same += ub - lb;
            arcWin += M - ub;
            hiWin += lb;
        }

        bw.write(String.valueOf(hiWin + " " + arcWin + " " + same));
        bw.flush();
        bw.close();
        br.close();
    }
}