[코드트리] 겹치지 않게 선분 고르기 2
T
TikaToka
DP 연습을 하는 도중에 만난 문제이다. 문제를 이해하고 나면 되게 쉽게 풀 수 있는 문제지만, 나 같은 경우에는 스스로 의문속에 갇혀 해결에 어려움을 겪은 케이스였다
처음 생각한 잘못된 생각들
1.
시작점에 대해 정렬
추가정보
그냥 시간의 흐름 (결론적으로) 흐름에 맞게 정렬되면 문제가 없기 떄문에, 시작점 기준으로 정렬해도 무관.
2.
dp를 기록할 때, 기존에 어떤 선분들은 선택했는지에 대한 정보를 같이 가지고 있어야 한다.
하지만 2번이 불필요하다는 것을 알게 되면 1번이 잘못된 것임을 알 수 있다.
2번이 불필요 한 이유:
dp를 선분 i를 표함하는 최대 선택 가능한 선분 개수를 저장
끝점 기준으로 정렬하면 i 이전 선분들 중에서 i와 겹치지 않는 선분만 고려할 수 있음.
또한, dp에는 최적해만을 저장하게 되기 때문에, 다시 말해 최적 부분 구조와 중복된 하위 문제의 효율적 계산이라는 dp의 특성때문에, 항상 겹치지 않는 선분들을 선택하게 되고, 그중 최선의 결과를 저장하게 되므로 기존의 선택들을 고려할 필요가 없음
만약 idx가 필요하면 추적 필요
Solution
n = int(input())
dp = [1 for _ in range(n)]
board = []
for i in range(n):
a, b = map(int, input().split())
board.append((a, b))
board.sort(key=lambda x: x[1])
for i in range(1, n):
for j in range(0, i):
if board[j][1] < board[i][0]:
dp[i] = max(dp[i], dp[j] + 1)
print(max(dp))
