[Code Tree] 겹치지 않게 선분 고르기 [Python]

문제

https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-select-segments-without-overlap-2/description

겹치지 않게 선분 고르기 2 설명 | 코드트리

 

---

풀이

문제 요약

수직선 상의 N개의 선분을 겹치지 않도록 최대한 많은 선분을 선택하자.

아이디어

우선 주어진 선분이 정렬되어있다는 보장이 없다.

정렬을 한 후 임의의 선분에 대해 이전 선분을 선택했을 때보다 더 많은 선분을 선택할 수 있는지 확인해야 한다.

점화식은 다음과 같다.

dp[i] : i번째 선분의 끝 점을 기준으로 지금까지 선택한 최대 선분의 수

모든 선분에 대해 dp[i] = 1로 시작할 수 있다.

n = int(input())
x = [tuple(map(int, input().split())) for _ in range(n)]

# Please write your code here.

dp = [1] * n
x.sort()

for start in range(n):
    for end in range(start):
        if x[end][1] < x[start][0]:
            dp[start] = max(dp[start], dp[end] + 1)

print(max(dp))

풀이 시간

5분

---

소스코드

https://github.com/rogi-rogi/problem-solving/blob/main/code-tree/Algorithm Intro/DP I/17 겹치지 않게 선분 고르기 2(challenge-select-segments-without-overlap-2).py

problem-solving/code-tree/Algorithm Intro/DP I/17 겹치지 않게 선분 고르기 2(challenge-select-segments-without-overlap-