[백준] 2352 반도체 설계

📖 문제

---

🧑🏻‍💻 풀이 과정

1) 문제 접근 및 이해

연결선들이 서로 꼬이지 않기 위해서는 다음 연결하는 포트가 이전에 연결된 포트보다 항상 큰 번호에 연결이 되어야합니다.

이러한 조건을 만족하는 내용은 LIS(최장 증가 부분 수열)를 탐색해야하는 문제입니다.

정확한 연결된 번호를 구하는 것이 아니라 가장 긴 길이를 구하면 되므로 이분탐색을 이용하였습니다.

2) 알고리즘

• LIS (최장 증가 부분 수열)
• 이분탐색

3) 풀이 코드

사용 언어 - Python

import sys
sys.stdin = open('input.txt')

def solution(left, right, target):
    if left > right:                                                # 탐색 종료
        return left
    
    mid = (left+right) // 2                                         # 중간 인덱스 값

    if answer[mid] < target:                                        # 이분 탐색
        return solution(mid+1, right, target)
    elif answer[mid] > target:
        return solution(left, mid-1, target)

N = int(sys.stdin.readline())                                       # 포트 개수
ports = list(map(int, sys.stdin.readline().split()))                # 각 포트가 연결될 반대편 포트 번호

answer = [ports[0]]                                                 

for i in range(1, N):
    if answer[-1] < ports[i]:                                       # 다음 포트 연결이 꼬이지 않는다면
        answer.append(ports[i])                                     # 정답 목록에 추가
    else:                                                           # 꼬이게 된다면 이분탐색으로 이전값 변경
        answer[solution(0, len(answer)-1, ports[i])] = ports[i]     
    
print(len(answer))

---

🔗 문제 링크

- https://www.acmicpc.net/problem/2352

2352번: 반도체 설계

 

 

※ 오류 및 오타, 다른 의견이 있는 경우 댓글을 남겨주시면 감사하겠습니다