최적화 문제 결정 문제로 풀기

문제

프로그래머스

프로그래머스

 

---

 

재정의

두 문제 다 최적화 값을 구하는 문제이다.

값을 보면 알겠지만, 크키가 괴랄해서 시간복잡도를 N이하로 줄여야함을 알 수 있다.

 

최적화 문제를 결정문제로 푼다는 것은 다음을 의미 한다.

• 범위의 최솟값, 최댓값을 결정할 수 있다. (해의 구간을 알 수 있다.)
• input값의 변화에 대해 output의 결과가 선형 적이다.

 

위의 조건을 충족하면, 제약을 만족하는 값을 일일이 넣어서 테스트 할 수 있다.

input과 ouput의 관계가 선형적이라면, 이분 탐색을 통해서 빠르게 테스트를 할 수 있다.

이를 파라미터 서치, 최적화 결정 문제라고 정의한다.

 

---

 

입국심사

최소는 0, 최대시간은 가장 짧은 사람에게 모두가 맡길 때 이다.

여기서 시간은 선형적이다. 시간을 늘리면 처리할 수 있는 손님이 늘어난다.

시간을 줄이면 처리할 수 있는 손님이 줄어든다.

가능한 시간의 구간을 알고 있고, 시간에 대한 손님의 관계는 선형적이기 때문에 결정 문제로 변환하여 풀 수 있다.

 

def solution(n, times):
    def is_judge(time: int) -> bool:
        user = n
        for i in times:
            user -= (time // i)
        
        return user <= 0
      
    st, ed = 0, min(times) * n
    ret = float('inf')
    
    while st <= ed:
        mid = (st+ed) // 2
        # 해당 시간 내에 인원 처리가 가능한 경우
        if is_judge(mid):
            ret = min(ret, mid)
            ed = mid - 1
        # 해당 시간 내에 인원 처리가 불가능한 경우
        else:
            st = mid + 1
    
    return ret

 

---

 

징검다리

최소는 1, 최대는 0부터 distance 까지이므로 distance이다.

최소 거리를 길게 잡으면, 돌을 많이 없애야 한다.

최소 거리를 짧게 잡으면, 돌을 적게 없애야 한다.

가능한 최소 거리의 구간을 알고 있고, 최소 거리와 제거되는 돌은 선형적이므로 결정문제로 해결할 수 있다.

 

def solution(distance, rocks, n):
    def is_judge(dis):
        pre_rock = 0
        remove_cnt = 0
        
        for rock in rocks:
            distance = rock - pre_rock
            if distance < dis:
                remove_cnt += 1
            else:
                pre_rock = rock
            
            if remove_cnt > n:
                break
        
        return remove_cnt <= n
                
    
    rocks = sorted(rocks) + [distance]
    st = 0
    ed = distance
    
    while st <= ed:
        mid = (st+ed) // 2
        
        if is_judge(mid):
            ans = mid
            st = mid+1
        else:
            ed = mid-1
    
    return ans