개념은 다른 블로그에 잘 나와있어서,, 문제풀이 하면서 도저히 이해안되는것들 주절주절..끄적여봄
자력으로 푼게 하나도없음.
생소하고 어려운 개념임
뭘..결정한다?
그것부터가 진짜 뭐라는지 모르겠음.
하.. 나는 골드풀기에는 아직 멀었다...
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): 모든 비디오를 하나의 블루레이에 담았을 때 크기이므로 최대값을 설정
- 최대값으로 설정하기 딱좋음. 다 더한것보다 큰 블루레이는 필요없음.
아 .. 어려워 .. .뭐라는거야..
알겠는데 모르겠음
이걸 어떻게 바로바로 알아챌까..
연습뿐만이 살 길,,,
728x90
'☁️2024,2025☁️ > Algorithm' 카테고리의 다른 글
| 프로그래머스 문제풀이 2,3,4,5주차 - 클클 알고리즘 TF 정리 (3) | 2024.04.18 |
|---|