[BOJ][Python3/PyPy3] 17503 - 맥주축제 (이분탐색, 그리디)

교내 동아리에서 진행한 알고리즘 스터디에서 '우선순위 큐' 의 연습문제로 주어졌던 문제이다.

우선순위 큐를 사용하기 전에 제일 먼저 떠오른 풀이는 '이분 탐색'

아니나 다를까 문제 알고리즘 분류에도 '이분 탐색'이 있었다.

이분 탐색은 항상 익숙하지 않고 힘들었기에, 오랜만에 연습해보기 좋은 문제라고 생각했다.

 

내가 떠올린 아이디어는 '맥주의 선호도' 값을 기준으로 정렬하고

설정한 맥주의 도수보다 작은 맥주 중, 선호도가 높은 것들만을 그리디하게 뽑아서 선호도의 합을 구하는 것이다.

그리고 맥주의 도수를 기준으로 이분탐색을 진행하여 가능한 최소 도수를 구하고

최소 도수가 없다면 -1을 출력하도록 하면 된다

def check(mid):
    global kind, day, sum_taste
    s = 0
    cnt = 0
    for i in range(kind):
        if cnt == day:
            break
        if beer[i][1] <= mid:
            s += beer[i][0]
            cnt += 1
    if cnt != day or s < sum_taste:
        return False
    else:
        return True


day, sum_taste, kind = map(int, input().split())
min_alch = 10000000000
max_alch = 0
beer = []
for _ in range(kind):
    taste, alch = map(int, sys.stdin.readline().split())
    beer.append((taste, alch))
    if alch > max_alch:
        max_alch = alch
    if alch < min_alch:
        min_alch = alch
beer.sort(key=lambda x: -x[0])
binary_search(min_alch,max_alch)

여기에 이분탐색을 진행할 함수를 작성하였다.

def binary_search(start, end):
    while start < end:
        mid = (start+end)//2  # alchol
        if check(mid):
            end = mid - 1
        else:
            if start == mid:
                if check(end):
                    end = mid
                else:
                    mid = end
            start = mid
    if start == min_alch and check(start):
        print(start)
    elif start == max_alch and not check(start):
        print(-1)
    elif start == max_alch and check(start):
        print(start)
    else:
        print(start+1)

 

이번에 함수를 작성하면서 갖고 있던 오해를 풀 수 있었다.

나는 내가 원하는 맥주의 도수 값보다 작은 값이 등장하는 가장 큰 인덱스를 구하고자 하였고

이것이 Lower Bound 라고 생각을 했었다.

(Lower Bound는 구하려는 값 이상의 값이 맨 처음 등장하는 인덱스이었다.)

그리고 위 코드는 그걸 기어코 구현해내어 정답을 맞춘 코드이다.

 

 

처음에는 수많은 "틀렸습니다"에 직면해야 했다.

def binary_search(start, end):
    while start < end:
        mid = (start+end)//2 
        if check(mid):
            end = mid - 1
        else: 
            if start == mid:
                mid = start + 1
            start = mid
    if start == min_alch and check(start):
        print(start)
    elif start == max_alch and not check(start): 
        print(-1)
    elif start == max_alch and check(start):
        print(start)
    else:
        print(start+1)

이 코드는 아무리 제출해도 틀렸습니다를 받던 코드였고, 그 이유를 알 수 없었다.

그 이유는 결국 함수의 목적에 맞지 않는 코드를 작성하였기 때문이었다.

if start == mid:
	mid = start + 1 ## mid = end

7행의 이 코드를 작성한 이유는

만약 start = 2, end = 3 일 경우 mid = 2 가 되어

이 코드가 없는 상태에서 check 함수의 결과가 False가 나온다면 무한 루프를 돌기 때문이다.

 

나는 이 상황에서는 강제로 start 값을 end값과 맞춰버리도록 했다.

왜냐하면 (start = mid 였으므로) start 값을 기준으로 체크한 결과가 거짓이라면

당연히 마지막으로는 end값으로 체크봐야 하므로

일단 start = end로 만들어 루프를 나간 후

그 아래 조건 문으로 end값을 기준으로 체크시켜 그에 따라 결과가 나오도록 하면 된다고 생각하였기 때문이다.

 

문제는 여기에서 발생하였다.

이 함수의 목적은 "찾아야 하는 값의 바로 직전 인덱스를 찾는 것" 이다.

그런데 만약 start 에서 안되서 end만 검사하면 된다고 바로 검사하는 경우 다음과 같은 상황이 발생한다.

 

만약 end가 거짓일 경우 => 이 함수의 목적에 맞는다.

 

만약 end가 참일 경우 => 이 함수의 목적에 맞지 않는다.

반복문의 결과로 나온 start 값이 "키값"이었기 때문이다.

 

"상관 없지 않나? 그 아래에 if문에서 체크하잖는가"

나도 이렇게 생각해서 틀린 부분을 찾지 못했다.

 

그 아래 if문을 작성한 목적은

만약 찾아야 하는 값의 바로 직전 인덱스가 좌측끝값이나 우측 끝값일 경우

그냥 print( 찾은 값 인덱스 + 1) 을 시킬 수 없기 때문에 예외 처리를 해준 것인데,

 

반복문의 결과로 나온 start 값이 좌측 끝값이나 우측끝값이 아닌상태에서 "키값"이 도출된 경우

여지없이 print( 찾은 값 인덱스 + 1)를 시켜버리게 된다.

 

이 같이 사고한 이유는 나태한 본성 때문이 아닌지 반성하게 된다.

"아 몰라. 대충 이렇게 해서 어쩌다 저쩌다 때려맞으면 그것도 맞은 거지 뭐"

"기존에 작성한 코드 목적에는 맞지 않는 결괏값이지만, 부차적인 이유로 우연히 들어맞으면 그것도 맞은 거지 뭐"

 

이 문제를 풀면서 이 태도를 고치는 좋은 계기가 되었다.

 

그리고 다른 사람의 이분탐색 코드를 검색해보았다.

그리고 그 코드의 아이디어를 내 코드에 옮겨보았다.

def binary_search(start, end):
    global answer
    while start <= end:
        mid = (start+end)//2  # alchol
        if check(mid):
            end = mid - 1
            answer = min(answer,mid)
        else:
            start = mid + 1

매우 허무했다. 쓰잘데기 없는 분기문 하나 없이 깔끔한 코드였다.

mid값에서 가능하다면, mid값을 활용해 정답을 갱신한다.

그리고 그 값을 뺀 채 나머지로 재탐색한다.

mid값에서 안된다면 그건 그냥 안된걸로 빼고 다시 탐색한다.

 

매우 심플하다.

최솟값 갱신을 저렇게 할 수도 있구나, 이분탐색을 이렇게 깔끔하게 할 수도 있구나

두가지 아이디어를 배울 수 있었다.

 

다음으로는 이 문제를 본래 스터디 주제에 맞게 우선순위 큐로 풀어보고자 한다.