문제
2565번: 전깃줄
첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는
www.acmicpc.net
풀이
전깃줄이 어떤 상황에 교차되는지 따져보면 금방 LIS 문제라는 것을 알 수 있다. 따라서 전선을 나타내는 리스트를 만들어 가장 긴 증가하는 부분수열을 찾아주면 된다.
N = int(input())
graph = [0]*501
for _ in range(N):
a,b = map(int,input().split())
graph[a] = b
dp = [1]*501
for i in range(1,501):
for j in range(1,i):
if 0 < graph[j] < graph[i]:
dp[i] = max(dp[i],dp[j]+1)
print(N-max(dp))'PS > 백준' 카테고리의 다른 글
| 12865번 - 평범한 배낭 (0) | 2022.11.04 |
|---|---|
| 9251번 - LCS (0) | 2022.11.04 |
| 11054번 - 가장 긴 바이토닉 부분 수열 (0) | 2022.11.04 |
| 11053번 - 가장 긴 증가하는 부분 수열 (0) | 2022.11.04 |
| 2156번 - 포도주 시식 (0) | 2022.10.22 |