이것이 코딩 테스트다 | 떡볶이 떡 만들기

난이도 : 🌕🌕 | 풀이 시간 : 40분 | 시간 제한 : 2초 | 메모리 제한 : 129MB

이게 왜 난이도 2인지 모르겠음. 문제를 이해하는데 시간이 많이 걸렸다!

문제

오늘 동빈이는 여행 가신 부모님을 대신해서 떡집 일을 하기로 했다. 오늘은 떡볶이 떡을 만드는 날이다. 동빈이네 떡볶이 떡은 재밌게도 떡볶이 떡의 길이가 일정하지 않다. 대신에 한 봉지 안에 들어 가는 떡의 총 길이는 절단기로 잘라서 맞춰준다.
절단기에 높이(H)를 지정하면 줄지어진 떡을 한 번에 절단한다. 높이가 H보다 긴 떡은 H 위의 부분이 잘릴 것이고, 낮은 떡은 잘리지 않는다.
예를 들어 높이가 19, 14, 10, 17cm인 떡이 나란히 있고 절단기 높이를 15cm로 지정하면 자른 뒤 떡의 높이는 15, 14, 10, 15cm가 될 것이다. 잘린 떡의 길이는 차례대로 4, 0, 0, 2cm이다. 손님은 6cm 만큼의 길이를 가져간다.
손님이 왔을 때 요청한 총 길이가 M일 때 적어도 M만큼의 떡을 얻기 위해 절단기에 설정할 수 있는 높이의 최댓값을 구하는 프로그램을 작성하시오.

요약 |
각기 다른 N개의 떡 길이를 절단기 높이(H) 만큼 자르고,
자른 나머지 합(M)을 손님이 가져가는데(이게 손님이 원하는 길이임)
적어도 자른 나머지 떡 길이의 합(M) 만큼 얻기 위한
절단기 높이(H)의 최댓값을 구해라

입력 조건

• 첫째 줄에 떡의 개수 N과 요청한 떡의 길이 M이 주어진다.
  (1 <= N <= 1,000,000, 1 <= M <= 2,000,000,000)
• 둘째 줄에는 떡의 개별 높이가 주어진다. 떡 높이의 총합은 항상 M 이상이므로, 손님은 필요한 양만큼 떡을 사갈 수 있다. 높이는 10억보다 작거나 같은 양의 정수 또는 0이다.

절단기의 높이(우리가 탐색해야하는 범위)는 1 ~ 10억까지 정수 중 하나다.
우리는 10억 같이 매우 큰 수를 보면 이진탐색을 떠올려야 한다! 나동빈님이 그러셨음.

이 문제에서 절단기의 높이가 한정적이라면 순차 탐색으로 해결 할 수 있지만, 10억까지 정수이므로 순차 탐색은 분명 시간 초과가 걸린다.

따라서 이진탐색을 사용해야함 !

출력 조건

적어도 M만큼의 떡을 집에 가져가기 위해 절단기에 설정할 수 있는 높이의 최댓값을 출력한다.

높이의 최대값을 구한다는 것은 범위 내에서 조건을 만족하는 가장 큰 값을 찾는 최적화 문제다. 이 경우 파라메트릭 서치 기법을 사용하는데, 이는 최적화 문제를 결정 문제(yes or no)로 바꾸어 해결하는 기법이다.

보통 파라메스틱 서치 유형은 이진 탐색을 이용하여 해결한다.

범위 내에 조건을 만족하는 값을 찾는 문제 -> 파라메트릭 서치 이용
파라메트릭 서치 -> 이진 탐색 이용

문제 해결 과정

이진 탐색은 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 것이다.

이 문제에서 우리가 찾으려는 데이터는 적어도 자른 떡의 길이 합을 얻기 위한 절단기의 높이(H)이다.

절단기의 높이는 0부터 우리가 갖고 있는 떡 중 제일 긴 떡의 길이 안에 있어야 떡을 자를수 있다. 따라서 절단기 높이의 범위는 0부터 max(떡길이)이다.

• 떡의 개수 (N) = 4개
• 각 떡의 길이 (array) = 19, 15, 10, 17
• 손님이 원하는 떡의 길이(잘린 떡) (M) = 6cm

이라고 할 때, start / mid / end 를 위 범위를 통해 구해보면

start : 0 mid : 9 end : 19 이다.

(+ mid는 중간점으로, 시작점과 끝점의 합을 2로 나누고, 소수점을 날린 것이다.)

우리는 세 개의 경우의 수를 생각할 수가 있다.

• 잘린 떡의 합이 M보다 작을 경우
• 잘린 떡의 합이 M보다 크거나 같을 경우
• 잘린 떡의 합이 M과 같을 경우

*잘떡합 : 잘린 떡의 합, 손떡 : 손님이 원하는 길이의 떡

1) 잘떡합이 손떡보다 크거나 같을 경우 ( Total >= M )

잘떡합이 손떡(M) 보다 크거나 같은 경우 -> 손떡(M) 만큼의 길이는 얻을 수 있으니 일단 킵한다. 우리가 원하는 값을 찾을 때 까지 반복하면서 변수에 저장해둔다.

위의 예시로 다시 돌아가서,
잘린 떡의 합을 구하려면 떡의 길이 - mid 를 구하고 모두 합해야한다.

본 예시의 경우 mid = 9 이므로,
첫 번째 이진 탐색에서의 잘떡합은 (19 - 9) + (15 - 9) + (10 - 9) + (17 - 9) = 25이다.

step1

여기서 우리가 생각해야할 것은 잘떡합이 손떡에 가까워지려면 어디로 이동해야하는가? 이다.

잘떡합(25cm)이 손떡(6cm)에 더 가까워지려면, 0부터 mid까지의 길이.
그러니까 절단기 높이가 길어져야 한다. 그래야 잘린 나머지 떡들의 합이 작아지기 때문이다.

절단기의 높이를 길어지게 하려면 오른쪽 방향으로 탐색을 해야한다. 즉, 왼쪽을 날려버려도 상관이 없다.

따라서 우리의 시작점이 중간점 + 1 이 된다.

>> start = mid + 1

step 2

start : 10 (mid + 1) mid : 14 (10+19/2) end : 19
잘떡합 = 9

step 3

start : 15 (mid + 1) mid : 17 (15+19/2) end : 19
잘떡합 = 2

위에서 설명한 내용으로 계속해서 이진 탐색을 진행하다, 이제 잘떡합이 손떡(M)보다 작은 경우가 나왔다. 이럴 때는 어떻게 해야할까?

2) 잘떡합이 손떡보다 작을 경우 ( Total < M )

잘떡합이 손떡(M)보다 작은 경우는 나머지 떡의 길이의 합이 손님이 원하는 떡의 길이 보다 짧다는 것이다.

이를 해결하기 위해서는 절단기의 높이를 낮추어, 나머지 떡의 길이가 더 길어지도록 해야한다.

절단기의 높이를 짧아지게 하려면 step 3의 mid 이하에 절단기의 위치가 있어야 하기 때문에 왼쪽 방향으로 탐색을 해야한다. 즉, 오른쪽을 날린다!

따라서 우리의 끝점이 중간점 - 1이 된다.

>> end = mid - 1

3) 잘떡합이 손떡의 길이와 같을 경우 ( Total == M )

정답을 찾은 경우다. Good >___<

start : 15 mid : 15 (15+16/2) end : 16 (mid - 1)
잘떡합 = 6

따라서 위와 같은 과정을 거쳐 절단기 높이가 15일때 적어도 6cm인 떡의 길이를 얻을 수 있는 것을 알았다.

이제 우리는 위 과정을 코드로 구현해 볼 것이다!

코드 구현

n,m = map(int, input().split())
# n : 떡볶이의 개수
# m : 손님이 원하는 떡의 길이 (aka. 손떡)

array = list(map(int, input().split()))
# 각 떡볶이들의 길이

start = 0
end = max(array)
# 시작점 : 0 
# 끝점 : 전체 떡 길이 중 가장 긴 떡의 길이

result = 0
# 적어도 m길이의 떡을 얻을 수 있는 mid 값(절단기의 높이)을 저장 할 변수

while start <= end: # 시작점이 꿑점보다 작거나 같은 경우 무한 루프 실행
    total = 0 # 잘린 나머지 떡들의 합(aka. 잘떡합)    
    mid = (start + end)//2 # 중간값
    
    for x in array: # 각 떡볶이 길이들의 요소 하나씩 불러옴
        if x > mid: # 떡볶이 길이가 절단기 높이 보다 크면 (그래야 자를 수 있으니까)
            total += x - mid
            # 떡볶이 길이 - 절단기 높이 = 나머지 떡 
            # 해서 총 합 구함

    if total < m: 
        # 잘떡합이 손떡보다 작을 경우 
        # 절단기의 높이를 낮추어 나머지 떡들의 길이가 길어지도록 해야함
        # (손떡과 값이 가까워지도록)
        end = mid - 1
        # 왼쪽 방향 탐색
        
    else: # 잘떡합이 손떡보다 크거나 같을 경우 
        result = mid
        # 적어도 손님이 원하는 길이의 떡을 가져갈 수 있기 때문에 결과에 저장해두고
        # 절단기의 높이를 높여 나머지 떡들의 길이가 짧아지도록 해야함
        # 계속 반복하여 절단기 높이의 최대값을 찾아줌
        # (손떡과 값이 가까워지도록)
        start = mid + 1
        # 오른쪽 방향 탐색
        
print(result)
# 결과 절단기의 높이 출력
        

공부 한 책 | 이것이 코딩테스트다 with 파이썬