주어진 문제를 결정문제로 변형하여 이분탐색을 통해 해결하는 것
파라메트릭 탐색은 모든 문제에 적용할 수 없고, 아래의 세 조건을 만족해야 함
구하고자 하는 값의 범위를 start와 end로 크게 두고,
조건문을 이용하여 해당 문제의 유효한 범위인지를 파악하고,
조건이 만족되면 start와 end를 점점 좁혀가는 방식으로 구현
연료 탱크의 상태를 문자열로 입력받고, 연료량을 %로 표현하는 문제
######____
60%
입력되는 문자열의 길이는 항상 10개로 고정되어 있음
fuel = input() # 연료량을 입력받음
start, end = 0, 9
Max = 0 # 최대값을 넣을 변수 생성
while start <= end:
mid = (start+end)//2
if fuel[mid]=='#':
start = mid + 1
Max = mid # 최댓값 갱신
else:
end = mid - 1
print(f'{(Max+1)*10}%')
fuel의 갯수는 10으로 고정되어 있으므로 위와 같이 초기 범위를 0 ~ 9로 두고, mid를 중간값으로 설정한다.
while문 내의 조건문을 통해 fuel[mid]가 #인 경우, start를 mid+1로, 최댓값을 mid로 갱신하고, 그렇지 않은 경우 end를 mid-1로 조정하였다.
위 작업을 start와 end가 같아질 때까지 계속 반복하게 되면, 최댓값이 결정되게 된다.
하지만 위 문제에서 fuel가 하나도 없는 경우 즉, __________
인 경우, 10%라고 표시되는 버그가 발생한다.
이 경우 초기 Max값을 -1로 설정해주면, 위와 같은 버그는 해결된다.
fuel = input() # 연료량을 입력받음
start, end = 0, 9
Max = -1 # 최대값을 넣을 변수를 -1로 초기화
while start <= end:
mid = (start+end)//2
if fuel[mid]=='#':
start = mid + 1
Max = mid # 최댓값 갱신
else:
end = mid - 1
print(f'{(Max+1)*10}%')