lango

찍먹? 부먹?
난 부먹 개발자.

5 minute read




문제 풀이

이번 문제는 이분 탐색을 적절히 응용할 줄 알아야 한다.
먼저 문제의 패턴부터 살펴보자. 먼저 K개의 랜선을 동일한 길이의 N개의 랜선으로 잘라 만들어야 하는데, 이 때 최대로 가질 수 있는 길이를 구해야 한다.

예제와 같이 K=4, N=11이라고 한다면 4개의 랜선을 11개로 만들 수 있을 때 최대로 가질 수 있는 길이를 찾아보자.

  1. 만약 198의 크기로 자른다고 한다면
    802 길이를 가진 랜선은 198씩 4개,
    743 길이를 가진 랜선은 198씩 3개,
    457 길이를 가진 랜선은 198씩 2개,
    539 길이를 가진 랜선은 198씩 2개로 총 11개의 랜선을 가질 수 있고 이떄 랜선의 최대 길이는 198이다.

  2. 만약 199의 크기로 자른다고 한다면
    802 길이를 가진 랜선은 199씩 4개,
    743 길이를 가진 랜선은 199씩 3개,
    457 길이를 가진 랜선은 199씩 2개,
    539 길이를 가진 랜선은 199씩 2개로 총 11개의 랜선을 가질 수 있고 이떄 랜선의 최대 길이는 199이다.

  3. 만약 201의 크기로 자른다고 한다면
    802 길이를 가진 랜선은 201씩 3개,
    743 길이를 가진 랜선은 201씩 3개,
    457 길이를 가진 랜선은 201씩 2개,
    539 길이를 가진 랜선은 201씩 2개로 총 10개의 랜선을 가지게되어 11개를 만들 수가 없다.

  4. 만약 200의 크기로 자른다고 한다면
    802 길이를 가진 랜선은 200씩 4개,
    743 길이를 가진 랜선은 200씩 3개,
    457 길이를 가진 랜선은 200씩 2개,
    539 길이를 가진 랜선은 200씩 2개로 총 11개의 랜선을 가질 수 있고 이떄 랜선의 최대 길이는 200이다..

결국 11개의 랜선을 가질 때 200의 길이를 가져야 최대 길이가 됨을 알 수 있다.


아이디어 도출

이제 문재는 이분 탐색을 이용하여 최대로 가질 수 있는 길이를 어떻게 구할 수 있을까?
일반적으로 이분 탐색은 배열에서 원하는 인덱스를 찾기 위해서 사용하였다. 그런데 이 문제에서는 특정 인덱스가 아니라 문제 그대로 길이를 구해야 한다는 것이다.

  • 테스트케이스의 입력 범위는 int형의 상한 범위까지 주어질 수 있기 때문에 이분 탐색에 필요한 데이터들은 모두 long형으로 선언해야 한다.
  • 배열의 인덱스를 찾는 것이 아니기에 별도로 배열을 정렬할 필요는 없다.
  • 0부터 입력받은 랜선 중 가장 긴 길이를 가진 수만큼 이분 탐색을 진행한다.
    • mid(중간 길이) 값을 구한다.
      • 현재 탐색 범위에서 최소길이(min)와 최대길이(max)의 합을 2로 나누어 구한다. mid = (min + max) / 2
      • mid(중간 길이) 값이 0이 될 경우를 고려하여 min 값을 0이 아닌 1로 선언한다.
  • 이분 탐색을 통해 얻어낸 값에 -1은 최대길이가 된다.


아이디어는 좀 복잡해 보이는데 작성한 코드를 보며 하나씩 살펴보자.

1
2
3
4
5
6
7
8
9
10
11
12
13
14

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

int K = Integer.parseInt(st.nextToken());
int N = Integer.parseInt(st.nextToken());
int[] arr = new int[K];
long max = 0;

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

long min = 1;
long mid = 0;

K와 N을 입력받고 K개의 랜선 길이를 담을 배열을 선언한다.
그리고 K개의 랜선중 가장 긴 길이를 저장하기 위한 long형 max 변수를 선언하자.
다음으로 주어진 랜선의 길이들을 배열에 저장해가며, 가장 긴 랜선의 길이를 max에 저장한다.
마지막으로 이분 탐색에서 이용할 최소 길이를 가지는 min 변수와 중간 길이를 가지게 될 mid 변수를 long형으로 선언하고 각각 1, 0으로 초기화한다.

max, min, mid를 long형으로 초기화한 이유는?
문제의 요구사항을 보면 랜선의 길이는 2^31-1보다 작거나 같은 자연수라고 알려주고 있다. int형으로는 범위 초과가 발생할 수 있기 때문에 안전하게 long형으로 선언하여 사용하기 위함이다.

min의 초기값을 1로 설정한 이유는?
by zero 에러를 방지하기 위해 min을 1로 설정하였다. 예를 들어 K가 1이고, N이 1이며 입력받은 랜선의 길이 1이라고 한다면 min이 0이되고 max가 1이 되면서 중간 길이 값이 되는 mid가 0이 나오기에 연산을 수행할 때 0으로 나눗셈 연산이 되버리는 문제가 발생할 수 있다. (java.lang.ArithmeticException:/by zero 예외 발생)

마지막으로 이분 탐색 코드를 보자.

1
2
3
4
5
6
7
8
9
10
11
12

while(min <= max) {
    mid = (min + max) / 2; // 1
    int lengthCnt = 0; // 2

    for(int i=0; i<arr.lengthCnt; i++) {
        lengthCnt += arr[i] / mid; // 3
    }

    if(lengthCnt < N) max = mid - 1; // 4
    else min = mid + 1; // 5 
}
bw.write(min-1+"\n");

최소 길이부터 최대 길이까지 while문을 통해 반복하는데 안에서 수행할 내용은 다음과 같다.

  1. 먼저 중간 값을 구한다.
  2. 랜선을 잘라서 개수를 비교할 lengthCnt 변수를 선언한다.
  3. 중간 길이인 mid로 비교해야 하기 때문에 각 반복마다 for문을 통해 랜선마다 중간 길이로 잘라서 개수를 구한다.
  4. upper bound 형식을 적용한다.
    4.1. 중간 길이(mid)로 잘랐을 때 개수가 만들고자 하는 랜선의 개수보다 작다면(lengthCnt < N) 원하는 개수보다 잘라진 랜선들이 적다는 것이다. 즉, 하나의 잘라진 랜선이 너무 길기 때문에 더 짧게 잘라야 한다는 것을 의미한다. 그래서 자르고자 하는 길이를 줄이기 위해 최대 길이를 줄인다.
    4.2. 또한 중간길이(mid)로 잘랐을 때 개수가 만들고자 하는 랜선의 개수보다 크거나 같다면(lengthCnt > N) 원하는 개수보다 잘라진 랜선들이 많다는 것이다. 결국 잘라진 랜선이 너무 짧기에 더 길게 만들 수 있다는 것을 의미한다. 그래서 자르고자 하는 길이를 늘려야 하므로 최소 길이를 늘린다.

Upper Bound란?
Upper Bound는 찾고자 하는 값보다 큰 값이 처음으로 나타나는 위치이다. 결국 상한값을 찾는 것인데, 찾고자 하는 특정 값을 초과하는 ‘첫 위치’를 반환한다.

위 과정을 통해서 랜선의 개수가 중복될 때 최대 길이를 찾아야 하므로 Upper Bound를 통해 얻어진 값에서 -1을 해주면 최대 길이가 된다.

upper bound를 통해 얻어진 값에서 -1을 하는 이유?
예를 들어 arr=[1,2,2,2,3] 배열에서 찾을 key가 2라면 2를 초과하는 처음 위치는 3인데 이는 arr[4], 즉 index로는 4이다. 문제에서는 중복되는 랜선 개수들 중 최대길이를 찾아야 했으므로 중복되는 랜선 개수들 중 가장 끝값(Upper Bound-1)이 최대길이가 되기 때문이다.



작성코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

class Main {
    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());
        
        int K = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken());
        int[] arr = new int[K];
        long max = 0;
        
        for(int i=0; i<K; i++) {
            arr[i] = Integer.parseInt(br.readLine());
            max = Math.max(max, arr[i]);
        }

        long min = 1;
        long mid = 0;

        while(min <= max) {
            mid = (min + max) / 2;
            int length = 0;

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

            if(length < N) max = mid - 1;
            else min = mid + 1;
        }
        
        bw.write(min-1+"\n");

        bw.flush();
        bw.close();
        br.close();
    }
}

회고

  • 이분 탐색을 이용해 찾고자 하는 값의 인덱스를 구하는 방식이 아닌, 랜선의 길이 자체를 구해야 했기에 아이디어를 생각하는데 어려움이 있었다.
  • 무턱대고 int형으로 문제를 풀었다가 틀리고, 연산 과정에서 중간값이 0이 되면서 틀리는 등 문제 풀이를 위한 알고리즘 구현도 중요하지만 알고리즘에 활용할 자료형의 범위도 충분히 고려하고 구현해야 한다고 느꼈다.

출처

  • 해당 문제의 저작권은 문제를 만든이에게 있으며 자세한 내용은 문제 링크에서 참조바랍니다.

참고

You may also enjoy