upperbound, lowerbound
1. 정의
upperbound : 처음으로 target 초과의 값이 나오는 것!
lowerbound : 처음으로 target 이상의 값이 나오는 것!
2. 예시
target이 3일때
| lowerbound | numbers | upperbound |
| 5 | v | |
| 3 | ||
| 3 | ||
| v | 3 | |
| 2 | ||
| 1 |
3. 문제에서의 활용
대부분의 lowerbound, upperbound 문제는 trade-off 관계에 있는 두 값(1.최소최대화 조건, 2.제한조건)이 주어진다.
이를 표로 정리하면 다음과 같다
| lowerbound | 1. 최소최대화 조건 | 2.제한 조건 | upperbound |
| c | 5 | v | |
| b | 3 | ||
| 3 | |||
| v | a | 3 | |
| 2 | |||
| 1 |
제한조건=3에서 최솟값을 찾아야 하면 lowerbound를 사용하여 최솟값인 a를 찾고,
최댓값을 찾아야 하면 upperbound를 사용하여 c를 찾고 -1을 더해줘서 최댓값인 b를 찾아준다.
2.제한조건은 보통 "1.최소최대 조건"을 input으로 하는 모듈의 return값으로 처리를 한다.
3. 예제(백준 2343 기타레슨)
위 예제의 trade-off 관계의 두 값은 블루레이의 길이(최소화조건)와 블루레이의 개수(제한조건)이다.
주어진 블루레이의 개수 조건을 만족하면서 블루레이의 길이를 최소화 해야한다.
이를 표로 나타내면 다음과 같다.
| 구해야 하는것 | 블루레이 길이 | 블루레이 개수 |
| 45 [ (1,2,3,4,5,6,7,8,9) ] | 1 | |
| 44 [ (1,2,3,4,5,6,7,8),(9) ] | 2 | |
| ... | ... | |
| 23 [ (1,2,3,4,5,6),(7,8,9) ] | 3 | |
| ... | ... | |
| v (=제한조건 3의 lowerbound) | 17 [ (1,2,3,4,5),(6,7),(8,9) ] | 3 |
| ... | ||
| 12 [ (1,2,3,4),(5,6),(7),(8),(9) ] | 5 | |
| 11 [ (1,2,3,4),(5,6),(7),(8),(9) ] | 5 | |
| 10 [ (1,2,3,4),(5),(6),(7),(8),(9) ] | 6 | |
| 9 [ (1,2,3),(4,5),(6),(7),(8),(9) ] | 6 |
즉 이 문제는 lowerbound 문제이다.
하지만 이해를 돕기위해 lowerbound와 upperbound로 각각의 방법으로 풀어 본다.
lowerbound
1. 풀이
블루레이 개수가 3이면서 블루레이의 최소크기를 찾는것은, (블루레이 개수=3)인 lowerbound를 찾는것과 같은 문제가 된다.
<=> 처음으로 3이상이 나오는 부분
2. 코드
import sys
N,M=map(int,input().split())
L=list(map(int,sys.stdin.readline().split()))
def cnt_blue(max_len):
now_len=0
cnt_blue=1
for size in L:
if max_len<size+now_len:
now_len=size
cnt_blue+=1
else:
now_len+=size
return cnt_blue
def lower_bound(target):
top = sum(L)
bot = max(L)
while(bot<top):
mid = (bot+top)//2
# print(bot, mid,top)
if target < cnt_blue(mid):
bot = mid+1
else:
top = mid
print(bot)
lower_bound(M)
3. 핵심
if target < cnt_blue(mid):
bot = mid+1
else:
top = mid타겟(3)보다 클때만 bot을 밀어올린다.
=> 그럼 3의 가장 아래부분이 찾아진다.
upperbound
1. 풀이
블루레이 개수가 3이면서 블루레이의 최소크기를 찾는것은, (블루레이 개수=4)인 upperbound를 찾는것과 같은 문제가 된다.
<=> 처음으로 3이상이 나오는 부분
2. 코드
import sys
N,M=map(int,input().split())
L=list(map(int,sys.stdin.readline().split()))
def cnt_blue(max_len):
now_len=0
cnt_blue=1
for size in L:
if max_len<size+now_len:
now_len=size
cnt_blue+=1
else:
now_len+=size
return cnt_blue
def upper_bound(target):
top = sum(L) + 1
bot = max(L)
while(bot<top):
mid = (bot+top)//2
if target+1<=cnt_blue(mid):
bot = mid+1
else:
top = mid
print(bot)
upper_bound(M)
3. 핵심
if target+1<=cnt_blue(mid):
bot = mid+1
else:
top = mid타겟(4)보다 크거나 같을때에도 bot을 밀어올린다.
=> 그럼 3의 가장 아래부분이 찾아진다.
* 제한조건 제일 윗부분의 upperbound는 없으므로 시작할때 top에는 +1을 꼭 해준다(top = sum(L) + 1)