Parametric Search BOJ (13397, 2343, 2805, 1654)

개념은 다른 블로그에 잘 나와있어서,, 문제풀이 하면서 도저히 이해안되는것들 주절주절..끄적여봄

자력으로 푼게 하나도없음.

생소하고 어려운 개념임

뭘..결정한다?

그것부터가 진짜 뭐라는지 모르겠음.

 

하.. 나는 골드풀기에는 아직 멀었다...

 

2805

# 적어도 M미터의 나무(M넘어도 됨)를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값?
import sys
N,M = map(int,sys.stdin.readline().split()) 
trees = list(map(int,sys.stdin.readline().split()))

def solution():
    start = 1
    end = max(trees)
    
    
    while start <=end:
        mid = (start+end)//2
        length = 0
        for i in trees:
            if i > mid: # 나무의 높이가 절단기의 높이보다 크다면 자른 나머지를 더한다.
                length += i-mid # 자른 길이 
        
        if length >= M: # 자른 길이가 M보다 크거나 같다면, 
            # 더 짧게 남길 수 있는지 
            start = mid + 1 #(절단기 높이 높임)
        else: # 자른 길이가 m보다 작은 길이면, 
            end = mid -1 # 더 길게 남길 수 있는지 확인하기 (절단기 높이 낮춤)

    print(end)

solution()

# 아.. 헷갈리고 어려워......

 

 

13397

골드.. mid값이 왜 구간 나눔의 기준이 되는지 모르겠었던 문제 

내가 생각했던거)

1. 구간을 나눈다. (어떻게..)

2. 나눈 구간별로 최댓값과 최솟값의 차를 구한다.

3. 구간별로 나온 값들을 정렬한다.

4. 정렬된 값들 중에서 가장 큰 값을 저장해놓는다.

5. 또 다른 구간을 나눠본다.

6. 2~5번을 반복한다.

7. 저장된 값 중에서 가장 작은 값을 출력한다.

여기에서 어떻게 parametric search를 적용해야할지 모르겠다.

아 ㄹ ㅇ 감도안잡힘

중간값을 무엇으로 해야하는지 모르겠으며, 무엇의 최대최소를 가깝게 해야하는가..

구간은 어떻게 나눠야 하는가..

---

- 구간을 나눌 기준 값을 변경해가면서 나눌 구간을 찾는다.

- 기준 값을 증가 or 감소시키면서 구간을 만들어주는데, 이 기준 값을 이분 탐색으로 구한다.

이해가 안되었던 점

-> 왜 mid를 이용해서 구간을 나누는지

 

# 지피티가 짜준..
import sys
# 입력 처리


def check(arr, mid, M):
    count = 1  # 최소 1개의 구간 필요
    min_val, max_val = arr[0], arr[0]

    for num in arr[1:]:
        min_val = min(min_val, num)
        max_val = max(max_val, num)

        if max_val - min_val > mid:
            count += 1  # 새 구간 시작
            min_val, max_val = num, num  # 새 구간 초기화

    return count <= M  # M개 이하로 나눌 수 있으면 True

def binary_search(M, arr):
    
    left, right = 0, max(arr) - min(arr)
    answer = right

    while left <= right:
        mid = (left + right) // 2

        if check(arr, mid, M):  # mid로 M개 이하 구간 만들 수 있음
            answer = mid
            right = mid - 1  # 더 작은 값 탐색
        else:
            left = mid + 1  # 더 큰 값 탐색

    return answer


N,M = map(int,sys.stdin.readline().split())
arr = list(map(int,sys.stdin.readline().split()))

# 결과 출력
print(binary_search(M,arr))

여기서 진짜 이해안되던게 mid다 mid..

 

 

우리는 "M개의 구간으로 나눌 때, 각 구간 내에서 (최대값 - 최소값)이 최소가 되도록 하고 싶다."

즉, 구간 내에서 값들의 최대-최소 차이가 특정 값 이하가 되도록 M개 이하로 나누는 것이 가능한지 확인하는 것이 목표라고...

 

우리가 찾고 싶은 값은 (최대-최소)의 최솟값이기 때문에,
즉, 모든 구간에서 (최대값 - 최소값) ≤ mid가 되는 가장 작은 mid를 찾아야 한다.

 

(최대값 - 최소값) 이  mid 이하가 되도록 , M개 이하로 나눌 수 있는지 확인을 해야 구간이 나눠진단다. 

 

이분 탐색을 쓰는 이유

• mid를 기준으로 나누는 이유는?
  → 특정 mid 값이 주어졌을 때, 그 mid 값 이하로 모든 구간을 나누는 것이 가능한지 확인하기 위해서야.
• mid가 너무 작으면?
  → 구간을 너무 많이 나누게 됨 (M보다 커짐 → False)
• mid가 너무 크면?
  → 적은 구간으로도 가능하므로, 더 작은 mid를 찾을 수 있음 (가능하면 더 줄이기 위해 right = mid - 1)

아 드럽게 어렵다아아ㅏ아악 ;;;;

 

또 도전해봤다. 

처참히 실패했다.

2343

# 블루레이의 크기를 최소로, M개의 블루레이는 모두 같은 크기
# 최대한 블루레이의 크기를 줄이는게 목표 , 최댓값중 최소값을 구해야함 
# 아까 그 골드문제다....

import sys 

N,M = map(int,sys.stdin.readline().split())
video = list(map(int,sys.stdin.readline().split()))



def check(video,mid,M):
    count = 1
    sum = 0
    for i in video:
        if sum+i > mid:
            # 다음 숫자로 넘어감, 블루레이 개수 추가
            count += 1
            sum = 0
        sum += i
    return count <= M

    

def binary_search(video,M):
    left = max(video)
    right = sum(video)
    answer = right

    while left <= right:
        mid = (left+right)//2
        if check(video,mid,M):
            answer = mid
            right = mid -1
        else:
            left = mid +1
    return answer

print(binary_search(video,M))

 

이게.. mid는 그렇다 쳐,,

근데 left right 의 기준을 잡는것도 빡세다.

 

• left = max(video): 가장 큰 비디오를 하나의 블루레이에 담을 수 있도록 최소값을 설정.
  • 만약에 1~9 까지 있으면, 블루레이 크기가 적어도 9는 되어야 함
  • 9보다 작으면, 하나의 비디오를 담을 수없음 

• right = sum(video): 모든 비디오를 하나의 블루레이에 담았을 때 크기이므로 최대값을 설정 
  • 최대값으로 설정하기 딱좋음. 다 더한것보다 큰 블루레이는 필요없음. 

 

 

 

아 .. 어려워 .. .뭐라는거야..

알겠는데 모르겠음

이걸 어떻게 바로바로 알아챌까..

연습뿐만이 살 길,,,