[2568] 전깃줄 -2

2023-04-25 | Algorithms / 백준 문제 풀이 모음 # Python, Platinum 5

백준 문제 풀이

문제 링크

2568번: 전깃줄 - 2

• 해설

    우선 문제에서 요구하는 것은 2가지이다.
    최소로 제거해야하는 전깃줄의 수와 제거할 전기줄의 번호이다.
      
    제거할 전깃줄의 수는 이분 탐색을 돌려서, 이전 길이(cnt-1)의 값이 현재 탐색하는 수보다 큰 경우
    cnt를 업데이트 하여서 최종 cnt 값을 모든 전깃줄 수에서 빼면 완료이다.
      
    여기까지 코드는 다음과 같다.
    import sys
      
    def bs(left, right, value):
        while(left <= right):
            mid = (left+right)//2
            if lis[mid] < value:
                left = mid + 1
            else:
                right = mid-1
        return left
      
    if __name__ == "__main__":
        N = int(sys.stdin.readline())
        elec = dict()
        keys = list()
        for i in range(N):
            a,b = map(int, sys.stdin.readline().split())
            keys.append(a)
            elec[a] = b
      
        cnt = 1
              
        keys.sort() // 이분탐색을 위해 정렬한다.
        lis = list(0 for _ in range(N))
        lis[0] = elec[keys[0]]
      
        for key in keys:
            value = elec[key]
            if lis[cnt-1] < value:
                lis[cnt] = value
                cnt += 1
            else:
                left = 0
                right = cnt
                ind = bs(left, right, value)
                lis[ind] = value
      
    		print(N-cnt)
  

  처음에는 cnt 업데이트 시 길이, 즉 수열이 증가하는 것이니까. 증가할 때마다 이전 수열과 값을 저장하고 나중에 출력하면 된다. 각각 lis[길이] 와 값을 비교할 때 분기처리가 되는데 각각 아래와 같이 추가하면, 겹치지 않는 최적의 수열을 구할 수 있다.

    if lis[길이] < elec[key]:
        group[cnt] = group[cnt-1][:]
        group[cnt].append(key)
    else:
        if ind > 0:
            group[ind] = group[ind-1][:]
            group[ind].append(key)
        else:
            group[ind] = [key]
  

  그 다음은 간단하다. group[cnt-1] 이 전깃줄이 겹치지 않는 최적의 수열이기때문에 해당 수열을 제외한 모든 값을 출력하면 된다.

• 답안

    import sys
      
    def bs(left, right, value):
        while(left <= right):
            mid = (left+right)//2
            if lis[mid] < value:
                left = mid + 1
            else:
                right = mid-1
        return left
      
    if __name__ == "__main__":
        N = int(sys.stdin.readline())
        elec = dict()
        keys = list()
        for i in range(N):
            a,b = map(int, sys.stdin.readline().split())
            keys.append(a)
            elec[a] = b
      
        cnt = 1
              
        keys.sort()
        lis = list(0 for _ in range(N))
        group = dict()
        lis[0] = elec[keys[0]]
      
        for key in keys:
            value = elec[key]
            if lis[cnt-1] < value:
                lis[cnt] = value
                group[cnt] = group[cnt-1][:]
                group[cnt].append(key)
                cnt += 1
            else:
                left = 0
                right = cnt
                ind = bs(left, right, value)
                lis[ind] = value
                if ind > 0:
                    group[ind] = group[ind-1][:]
                    group[ind].append(key)
                else:
                    group[ind] = [key]
                  
                  
      
        print(N-cnt)
      
        for k in keys:
            if k not in group[cnt-1][:]:
                print(k)