문제 링크
문제 풀이
- 정렬로 접근하다가 전에 이코테 강의에 있던 문제와 비슷하다고 생각되어 그 방식으로 접근해 보았다.
- 이 문제는 "가장 긴 증가하는 부분 수열" 문제로 생각할 수 있는데, a에 있는 전깃줄이 차례로 정렬되어 있을 때, b에 있는 전깃줄의 숫자가 차례로 정렬되어 있도록 하면 된다.
- 먼저 입력 받은 리스트를 a(x[0])를 기준으로 오름차순 정렬 후에, 같은 값이 있다면 b(x[1])를 기준으로 정렬한다.
- 이후 b에 있는 i번째의 전깃줄의 숫자(ab[i][1])가 그 이전의 숫자(ab[j][1])보다 크다면 1을 더하고(dp[j]+1), 이를 현재의 값(dp[i])과 비교하여 더 큰 값을 저장하도록 한다.
- 최종적으로 dp 리스트에 저장된 값중 가장 큰 값(max(dp))이 최대로 남아있을 수 있는 전깃줄의 개수가 되므로, 최소로 제거해야 할 전깃줄의 개수는 전체의 전깃줄의 수(n)에서 뺀 값이 된다.
전체 코드
import sys
n = int(sys.stdin.readline())
ab = []
for _ in range(n):
a, b = map(int, sys.stdin.readline().split())
ab.append([a, b])
ab.sort(key=lambda x: (x[0], x[1]))
dp = [1] * n
for i in range(1, n):
for j in range(i):
if ab[j][1] < ab[i][1]:
dp[i] = max(dp[i], dp[j]+1)
print(n - max(dp))
반응형
'Coding Test > BOJ' 카테고리의 다른 글
[백준/Python] 10026 적록색약 (0) | 2024.02.15 |
---|---|
[백준/Python] 12904 A와 B (2) | 2024.02.14 |
[백준/Python] 13335 트럭 (2) | 2024.02.12 |
[백준/Python] 2512 예산 (0) | 2024.02.10 |
[백준/Python] 7576 토마토 (0) | 2024.02.09 |