목록이분 탐색 (1)

Itmom's blog

[BOJ] 2352: 반도체 설계

문제: https://www.acmicpc.net/problem/2352 해법 입력으로 들어오는 숫자들을 다음과 같은 로직으로 stack에 넣는다. list의 top에 있는 숫자보다 현재 입력으로 들어온 숫자가 더 크다면 그대로 stack에 넣는다. list의 top에 있는 숫자보다 현재 입력으로 들어온 숫자가 더 작다면 list에서 이분 탐색으로 현재 입력된 숫자가 list의 sort를 깨트리지 않고 들어갈 수 있는 index를 찾은 뒤, 해당 index에 있던 숫자와 교환해준다. LIS 문제와 해법이 정확하게 똑같다. 위 예시처럼 숫자가 더 작은 포트를 연결하는 것이 이득인 경우가 있는 한편, 위 예시처럼 숫자가 더 작은 포트랑 연결되는 선이 있어도 연결하는 것이 손해인 경우도 있기에 LIS 문제인지..
Development/Algorithm 2022. 2. 26. 10:25
이전 Prev 1 Next 다음