2565. 전깃줄
2565번: 전깃줄
첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는
www.acmicpc.net
- 다른 사람 풀이
- 최장 증가수열이 가능한 최대개수를 찾아서 전체 전깃줄 수에서 뺀다
n=int(input())
graph=[list(map(int,input().split())) for _ in range(n)]
#1번 전봇대로 정렬
graph.sort(key=lambda x:x[0])
LIS=[1 for _ in range(n)]
#최장 증가수열
for i in range(n):
for j in range(i):
if graph[j][1]<graph[i][1]:
LIS[i]=max(LIS[i], LIS[j]+1)
print(n-max(LIS))'코딩테스트 > BOJ' 카테고리의 다른 글
| [백준] [다익스트라 알고리즘] 14938. 서강그라운드 (0) | 2023.05.09 |
|---|---|
| [백준] [위상정렬] 1516. 게임 개발 (0) | 2023.05.06 |
| [백준] [이진 탐색] [최장증가수열] 12015. 가장 긴 증가하는 부분 수열 2 (0) | 2023.05.06 |
| [백준] [BFS] 4963. 섬의 개수 (0) | 2023.05.02 |
| [백준] [구현] 7568. 덩치 (0) | 2023.05.01 |