Do what you wanna do

소요 시간: 32분
메모리: 25308KB
시간: 272ms

🔥 문제

돌섬과 탈출구 사이에는 총 n개의 작은 돌섬이 있다. n개의 작은 돌섬들 중 m개를 제거할때, 학생들이 각 돌섬을 점프한 최솟값을 최대한 크게 하려고 한다. 학생들은 탈출 시 n-m개의 모든 돌섬을 밟으면서 탈출해야 한다.

학생들이 갇힌 돌섬으로부터 탈출구까지의 거리 d가 주어지고, 각 n개의 작은 돌섬의 위치(갇힌 돌섬으로 부터의 거리)가 주어지며, 제거할 수 있는 작은 돌섬의 수 m이 주어질 때, m개를 제거한 후 학생들이 점프하는 최소거리의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에는 갇힌 돌섬으로부터 탈출구까지의 거리 d(1 ≤ d ≤ 1,000,000,000), 작은 돌섬의 수 n(0 ≤ n ≤ 50,000), 제거할 수 있는 작은 돌섬의 수 m (0 ≤ m ≤ n)이 공백으로 구분되어 주어진다.

두 번째 줄부터 n줄에 걸쳐서 갇힌섬으로부터 각 작은 돌섬이 얼마나 떨어져 있는지를 나타내는 하나의 정수가 한 줄에 하나씩 주어진다. (단, 두 돌섬은 같은 위치에 있을 수 없다.)

출력

m개의 작은섬을 제거한 뒤 학생들이 점프할 수 있는 최소거리의 최댓값을 출력한다.

🍀 풀이

배열`rockIslands`에 작은 돌섬들을 입력받고, 돌섬위치인 `0`을 추가한 후 오름차순 정렬하였다.

'돌섬 사이의 최소거리'를 기준으로 이분탐색 실행했다. `[0, d]`를 초기 범위로 이분탐색을 진행한다.

rockIslands[i] - rockIslands[j] (j < i)
1. `mid`보다 작다면 `i`돌섬을 제거한다.
2. `mid`보다 크거나 같다면, 조건에 만족하므로 학생들은 `j`돌섬으로 점프한다.(= `j`를 `i`로 갱신한다.)

그리고 제거한 돌섬이 `m`보다 많은지, 적은지에 따라 다음 이분탐색의 범위를 정한다.

1. `rockIslands`에 `0`을 넣고 이후는 돌섬의 위치를 저장하고, 입력을 다 받으면 오름차순 정렬한다.
2. `start`는 출발지점인 `0`, `end`는 도착지점인 `d`로 초기화시킨 후 이분탐색을 진행한다.
        1. `pt`는 학생들이 현재 위치해있는 돌섬의 인덱스를 저장하고(초기값=0), `count`는 제거하는 돌섬의 개수를 저장한다.
        2. `i` 첫번째 돌섬부터 순차적으로 탐색하며 제거할 돌섬을 찾는다.
                1. `pt`번째 돌섬에서 `i`번째 돌섬으로 가는 거리가 `mid`보다 크거나 같은 경우 `mid`가 점프하는 최소거리의 최댓값이 될 수 있으므로 학생들을 점프시킨다. `pt`값을 `i`로 갱신한다.
                2.  `pt`번째 돌섬에서 `i`번째 돌섬으로 가는 거리가 `mid`보다 작은 경우 `mid`가 점프하는 최소거리의 최댓값이 될 수 없으므로 거리를 늘리기 위해 돌섬을 제거한다. `count`값을 1 올린다.
        3. `count`가 `M`보다 크다면 제거해야할 돌섬 수보다 많이 제거한 것이므로 거리의 폭을 줄인다. `end`에 `mid-1`을 저장한다.
        4. `count`가 `M`보다 작거나 같다면 돌섬을 조건에 맞게 잘 제거한 것이므로 `answer`에 `mid`를 저장한다. 그리고 `start`에 `mid+1`을 저장한다.
3. `answer`를 출력한다.

💻 전체 코드

import java.io.BufferedReader;  
import java.io.InputStreamReader;  
import java.util.Arrays;  
import java.util.StringTokenizer;  
  
public class Main {  
  
    public static void main(String[] args) throws Exception {  
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");  
        int D = Integer.parseInt(st.nextToken());  
        int N = Integer.parseInt(st.nextToken());  
        int M = Integer.parseInt(st.nextToken());  
  
        int[] rockIslands = new int[N + 1];  
        for (int i = 1; i <= N; i++)  
            rockIslands[i] = Integer.parseInt(br.readLine());  
        Arrays.sort(rockIslands);  
  
        int start = 0;  
        int end = D;  
        int answer = 0;  
        while (start <= end) {  
            int mid = (start + end) / 2;  
            int pt = 0, count = 0;  
            for (int i = 1; i <= N; i++) {  
                if (mid <= rockIslands[i] - rockIslands[pt]) {  
                    pt = i;  
                } else {  
                    count++;  
                }  
            }  
  
            if (count > M) {  
                end = mid - 1;  
            } else {  
                answer = mid;  
                start = mid + 1;  
            }  
        }  
  
        System.out.println(answer);  
    }  
  
}

💫 리뷰

작은 돌섬이 정렬된다는 조건이 없었는데, 내가 혼자 그렇게 생각했다...ㅜ

앞으로 지레짐작하지 않기..!

소요 시간: 43분
메모리: 21692KB
시간: 228ms

🔥 문제

N개의 시험지를 현재 순서 그대로 K개의 그룹으로 나눈 뒤 각각의 그룹에 맞은 문제 개수의 합을 구하여 그 중 최솟값을 시험 점수로 하기로 하였다. 현수가 이번 시험에서 받을 수 있는 최대 점수를 계산하는 프로그램을 작성하자.

입력

첫 번째 줄에 시험지의 개수 N과 시험지를 나눌 그룹의 수 K가 정수로 주어진다. (1 ≤ K ≤ N ≤ 10^5)

두 번째 줄에 각 시험지마다 맞은 문제의 개수 x가 정수로 주어진다 (0 ≤ x ≤ 20)

출력

현수가 받을 수 있는 최대 점수를 출력한다.

🍥 풀이

8 2
12 7 19 20 17 14 9 10

이분탐색을 활용하여 정답을 찾아낼 수 있다.

이분탐색 시작값을 0, 끝값을 2000000(N의 최댓값*x의 최댓값)으로 설정해도 되고, 시작값은 맞은 시험 개수 최솟값인 '7'과 끝값은 전체 맞은 개수의 총합인 '108'로 설정해도 된다. 후자로 설정하면 이분탐색 실행 횟수를 줄일 수 있다.

시작값을 7, 끝값을 108로 설정한다면, mid값은 (108+7)/2 = 57이 될 것이다.

시험지 순서대로 처음부터 57 이상이 될 때까지 더해가며 그룹을 만들면, 그룹은 1개가 만들어진다.

[17, 14, 9, 10]은 합이 50이므로 그룹으로 만들 수 없다. 

그룹은 2개로 구성되어야 하는데, 1개만 만들어졌다. 그룹 수를 늘리기 위해서는 mid값을 줄여야한다!

mid를 줄이기 위해서는 끝값을 줄여야하고, 끝값을 mid-1로 갱신한다.

시작값을 7, 끝값이 56일 때, mid값은 31이 되고, 그룹은 3개가 만들어진다.

아까와는 반대로 그룹 수를 줄이기 위해서는 mid값을 늘려야한다! mid를 늘리기 위해서는 시작값을 늘려야하고, 시작값을 mid+1로 갱신한다.

시작값을 32, 끝값이 56일 때, mid값은 44이 되고, 그룹은 2개가 만들어진다.

그룹이 2개가 만들어졌지만, 44가 그룹 2개로 만들 수 있는 최대 점수라고 장담할 수 없다!

mid값을 늘려서 그룹 2개로 만들 수 있는 최댓값인지 확인한다. 시작값을 mid+1로 갱신한다.

계속 이분탐색을 하다보면,, 시작값이 51, 끝값이 52가 되는 경우가 나온다. mid값은 51이 되고, 그룹은 1개가 만들어진다.

그룹 수를 늘리기 위해서 끝값을 mid-1로 갱신한다.

시작값은 51, 끝값은 50이 되므로 이분탐색은 종료된다. 끝값을 기준으로 그룹을 만들어보면 2개가 만들어 지는 걸 확인할 수 있다.

이분 탐색 실행이 종료되면, 끝값이 그룹이 K개가 만들어질 때 최대 점수가 된다.

1. 시작값(0)과 끝값(20*100000)을 넣어 binarySearch 함수를 호출한다.
2. binarySearch 함수에서 이분탐색을 진행한다.
        1. `mid`는 그룹별로 맞은 문제 개수 중 최소값을 나타내며, `start`와 `end`의 평균값을 저장한다.
        2. `sum`은 그룹별로 맞은 문제 개수를 저장하고, `groupCount`는 그룹수를 저장한다.
        3. `n` 첫번째 시험지부터 순차적으로 탐색하며 그룹을 묶는다.
                1. `sum`에 현재 시험지에서 맞은 문제 개수를 더한다.(score[n])
                2. 만약 `mid`보다 `sum`이 크거나 같은 경우, 그룹을 만드는 조건에 부합하므로 `sum`을 0으로 초기화시키고 `groupCount`에 1을 더한다.
        4. `groupCount`가 `K`보다 크거나 같은 경우, 그룹별로 맞은 문제 개수 중 최소값이 현재보다 커야한다. 그러므로 `start`값을 `mid+1`로 갱신한다.
        5. `groupCount`가 `K`보다 작은 경우, 그룹별로 맞은 문제 개수 중 최소값이 현재보다 작아야한다. 그러므로 `end`값을 `mid-1`로 갱신한다.
        6. 이분탐색이 끝났다면, `end`를 반환하며 binarySearch 함수를 종료한다.
3.  binarySearch 함수 반환값을 출력한다.

💻 전체 코드

import java.io.BufferedReader;  
import java.io.InputStreamReader;  
import java.util.StringTokenizer;  
  
public class Main {  
    static int N, K;  
    static int[] score;  
  
    public static void main(String[] args) throws Exception {  
        init();  
        System.out.println(binarySearch(0, 2000000));  
    }  
  
    static void init() throws Exception {  
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");  
        N = Integer.parseInt(st.nextToken());  
        K = Integer.parseInt(st.nextToken());  
  
        st = new StringTokenizer(br.readLine(), " ");  
        score = new int[N];  
        for (int n = 0; n < N; n++) {  
            score[n] = Integer.parseInt(st.nextToken());  
        }  
    }  
  
    static int binarySearch(int start, int end) {  
        while (start <= end) {  
            int mid = (start + end) / 2;  
            int sum = 0, groupCount = 0;  
            for (int n = 0; n < N; n++) {  
                sum += score[n];  
                if (mid <= sum) {  
                    sum = 0;  
                    groupCount++;  
                }  
            }  
  
            if (K <= groupCount) {  
                start = mid + 1;  
            } else {  
                end = mid - 1;  
            }  
        }  
        return end;  
    }  
  
}

💫 리뷰

제자리 멀리뛰기 문제랑 접근 방식이 비슷해서 어렵지않게 풀 수 있었다.

<이분 탐색> 문제를 선택해서 풀었던거라,, 코테가서 이런 문제가 나왔을때 바로 이분 탐색을 떠올릴 수 있을지는 모르겠다..@_@

소요 시간: 33분
메모리: 29716KB
시간: 240ms

🔥 문제

길이가 N 미터이고, 높이가 H 미터인 동굴에 석순과 종유석이 번갈아가면서 있다. (N은 짝수이고, 석순 먼저 나타난다.)

개똥벌레가 한 구간을 정해 날아가면서 만나는 장애물들을 파괴한다.

개똥벌레가 파괴하는 장애물의 최솟값과 그러한 구간이 총 몇 개 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 H가 주어진다. N은 항상 짝수이다. (2 ≤ N ≤ 200,000, 2 ≤ H ≤ 500,000)

다음 N개 줄에는 장애물의 크기가 순서대로 주어진다. 장애물의 크기는 H보다 작은 양수이다.

출력

첫째 줄에 개똥벌레가 파괴해야 하는 장애물의 최솟값과 그러한 구간의 수를 공백으로 구분하여 출력한다.

🤔 풀이

6 7
1
5
3
3
5
1

위와 같은 입력이 들어왔다고 한다면, 동굴은 아래와 같은 그림이 될 것이다.

개똥벌레가 'h'높이로 날아간다고 하면, 석순은 `h`높이 이상인 석순의 수를 카운트하면 된다.

반면, 종유석은 위에서 내려오기 때문에 H-`h`+1 높이 이상인 종유석의 수를 카운트해야 한다.

즉, 개똥벌레가 'h' 높이로 날아가는 경우 높이가 h 이상인 석순과 H-h+1 이상인 종유석의 수를 더하면 개똥벌레가 부딪히는 장애물의 수가 된다.

높이가 x보다 큰 석순과 종유석을 구하기 위해서 누적합을 활용했다.

입력을 받으면서 석순과 종유석 높이에 해당하는 인덱스에 1을 더하고, 입력을 다 받은 후에 인덱스 내림차순으로 누적합을 했다.

1. 석순(`A`)와 종유석(`B`)를 순서대로 입력받는다.
2. 입력을 다 받은 후 석순과 종유석 배열 모두 누적합을 계산한다.
3. 동굴의 모든 높이를 확인하면서 해당 높이에 있는 석순과 종유석의 개수를 구한다.
4. 개똥벌레가 부딪히는 장애물 최솟값과 구간 수를 출력한다.

💻 전체 코드

import java.io.BufferedReader;  
import java.io.InputStreamReader;  
  
public class Main {  
  
    public static void main(String[] args) throws Exception {  
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
        String input = br.readLine().trim();  
        int N = Integer.parseInt(input.substring(0, input.indexOf(' ')));  
        int H = Integer.parseInt(input.substring(input.indexOf(' ') + 1));  
  
        int[] A = new int[H + 1];  
        int[] B = new int[H + 1];  
  
        for (int n = 0; n < N; n += 2) {  
            A[Integer.parseInt(br.readLine())]++;  
            B[Integer.parseInt(br.readLine())]++;  
        }  
  
        for (int h = H - 1; 0 < h; h--) {  
            A[h] += A[h + 1];  
            B[h] += B[h + 1];  
        }  
  
        int count = 0;  
        int min = N;  
  
        for (int h = H; 0 < h; h--) {  
            if (A[h] + B[H - h + 1] < min) {  
                count = 1;  
                min = A[h] + B[H - h + 1];  
            } else if (A[h] + B[H - h + 1] == min) {  
                count++;  
            }  
        }  
        System.out.println(min + " " + count);  
    }  
}

💫 리뷰

이분 탐색을 공부하기 위해 선택한 문제였는데,, 이분 탐색을 활용하지 않고 푸는게 시간이 더 짧았다..! w(°ｏ°)w