[Algorithm] 떡볶이 떡 만들기

문제

오늘 동빈이는 여행가신 부모님을 대신해서 떡집 일을 하기로 했다. 오늘은 떡볶이 떡을 만드는 날이다. 동빈이네 떡볶이떡은 재밌게도 떡볶이 떡의 길이가 일정하지 않다. 대신에 한 봉지 안에 들어가는 떡의 총 길이는 절단기로 잘라서 맞춰준다. 

절단기에 높이 H를 지정하면 줄지어진 떡을 한번에 절단한다. 높이가 H보다 긴 떡은 H 위의 부분이 잘릴 것이고, 낮은 떡은 잘리지 않는다.

예를 들어 높이가 19, 14, 10, 17cm인 떡이 나란히 있고 절단기 높이가 15cm로 지정하면 자른 뒤 떡의 높이는 15, 14, 10, 15cm가 될 것이다. 잘린 떡의 길이는 차례대로 4, 0, 0, 2cm이다. 손님은 6cm만큼의 길이를 가져간다.

손님이 왔을 때 요청한 총 길이가 M일 때, 적어도 M만큼의 떡을 얻기 위해 절단기에 설정할 수 있는 높이의 최대값을 구하는 프로그램을 작성하시오.

 

입력 조건

첫째 줄에 떡의 개수 N과 요청한 떡의 길이 M이 입력된다.

둘째 줄에 떡의 개별 높이가 주어진다.

 

출력 조건

적어도 M만큼의 떡을 집에 가져갈 수 있는 절단기의 높이 H를 출력한다.

 

풀이

가장 긴 떡의 길이를 절단기 높이로 두고, 줄여가면서 남는 떡의 길이를 M과 비교한다.

import java.util.*;

class Main {

  public static void main(String[] args) {
    
    int n, m;
    Scanner sc = new Scanner(System.in);
    n = sc.nextInt();
    m = sc.nextInt();
    int[] dduks = new int[n];
    for (int i = 0; i < n; i++)
      dduks[i] = sc.nextInt();
    sc.close();

    Arrays.sort(dduks);
    int h = dduks[n-1];
    while (true) {
      int sum = 0;
      for (int d : dduks) {
        if (d >= h) {
          sum += (d - h);
        }
      }
      if (sum == m) {
        break;
      }
      h--;
    } // end while

    System.out.println(h);

  } // end main
}

 

다른 풀이 (in 이것이 코딩테스트다 github)

        // 이진 탐색을 위한 시작점과 끝점 설정
        int start = 0;
        int end = (int) 1e9;
        // 이진 탐색 수행 (반복적)
        int result = 0; 
        while (start <= end) {
            long total = 0;
            int mid = (start + end) / 2;
            for (int i = 0; i < n; i++) {
                // 잘랐을 때의 떡의 양 계산
                if (arr[i] > mid) total += arr[i] - mid; 
            }
            if (total < m) { // 떡의 양이 부족한 경우 더 많이 자르기(왼쪽 부분 탐색)
                end = mid - 1;
            }
            else { // 떡의 양이 충분한 경우 덜 자르기(오른쪽 부분 탐색)
                result = mid; // 최대한 덜 잘랐을 때가 정답이므로, 여기에서 result에 기록 
                start = mid + 1;
            }
        }

배열에 대해서 이진 탐색을 시도한다. 시작점과 끝점을 설정한다.

start가 end(1e9 == 1 * 10^9, 아주 큰 수)보다 작거나 같을 때 반복적으로 수행한다.

start와 end의 중간 점을 mid에 저장한다. 떡의 길이가 저장된 배열을 탐색하는데,

mid보다 큰 길이를 가진 떡에 대해서만 잘라낸 나머지 값을 total에 더한다.

 

total이 M보다 작은 경우는 떡의 길이가 부족한 것이기 때문에, end에 mid-1을 저장하고 다시 시도한다.

 

total이 M보다 큰 경우는 떡의 길이가 충분하기 때문에 결과에 mid를 저장하고, start = mid+1로 절단기 높이를 높인다. 만약 정확한 높이를 찾았다면 start > end로 종료되면서 result를 높이 H로 반환하면 된다.

아닌 경우 start와 end 사이에서 다시 탐색을 진행한다.

 

결과

처음 풀었던대로 푼다면, 만약 떡의 길이가 아주 긴 떡이 있고 계속 줄여와야 한다면 엄청난 비효율을 가질 수 밖에 없다. 이진탐색 알고리즘을 사용한다면 중간 값으로 도약하면서 줄여가기 때문에 비효율에 대비할 수 있다.