[백준] 2565번 전깃줄 (LIS 문제)

사용 언어 - Python3

문제 -  2565번 전깃줄

LIS/LCS 문제 : 가장 긴 증가하는 부분 수열

LIS (Longest Incresing Subsequence)

LCS (Longest Common Subsequence)

 

https://www.acmicpc.net/problem/2565

2565번: 전깃줄

 

 

정답

전체 n개에서 LIS 빼주기

dp[i] = max(dp[i], dp[j]+1)

 

전봇대에 겹친다 =  A 전봇대 값이 작은 값 중에서, B전봇대 값이 더 크다.

안겹친다 =  A 전봇대 값이 작은 값 중에서, B전봇대 값이 더 작다 arr[i][0] > arr[j][0]

 

 A 전봇대 값이 작은 값 중에서 => arr.sort() A값을 기준으로 오름차순 정렬

 

해당 위치에서 나보다 더 작은 숫자가 있으면 dp 값을 업데이트해준다.

=> 나보다 작은 숫자가 여러 개 있다면, 자동으로 그 중 가장 큰 값 + 1

 

i	j	B값 비교 안겹치려면,[i][0] > [j][1] 만족	dp[i] 안 겹치는 전봇대의 개수
1	0	2 > 8 불만족(겹침)	1
2	0 1	9 > 8 만족 max(dp[2]=1,dp[0]+1) = 2 9 > 2 만족 max(dp[2]=2,dp[1]+1) = 2	2
3	0 1 2	1 > 8 불만족(겹침) 1 > 2 불만족(겹침) 1 > 9 불만족(겹침)	1
4	0 1 2 3	4 > 8 불만족(겹침) 4 > 2 max(dp[4]=1,dp[1]+1) = 2 4 > 9  불만족(겹침) 4 > 1 max(dp[4]=2,dp[3]+1) = 2	2
5	0 1 2 3 4	6 > 8 불만족(겹침) 6 > 2 max(dp[5]=1,dp[1]+1) = 2 6 > 9 불만족(겹침) 6 > 1 max(dp[5]=2,dp[3]+1) = 2  6 > 4 max(dp[5]=2,dp[4]+1) = 3	3
6	0 1 2 3 4 5	7 > 8 불만족(겹침) 7 > 2 max(dp[6]=1,dp[1]+1) = 2  7 > 9 불만족(겹침) 7 > 1 max(dp[6]=2,dp[3]+1) = 2  7 > 4 max(dp[6]=2,dp[4]+1) = 3 7 > 6 max(dp[6]=3,dp[5]+1) = 4	4
7	0 1 2 3 4 5 6	10 > 8 max(dp[7]=1,dp[0]+1) = 2 10 > 2 max(dp[7]=2,dp[1]+1) = 2 10 > 9 max(dp[7]=2,dp[2]+1) = 3 10 > 1 max(dp[7]=3,dp[3]+1) = 3 10 > 4 max(dp[7]=3,dp[4]+1) = 3 10 > 6 max(dp[7]=3,dp[5]+1) = 4 10 > 7 max(dp[7]=3,dp[6]+1) = 5	5

n = int(input()) # 전깃줄의 개수
arr = [list(map(int,input().split())) for _ in range(n)] # 연결된 전깃줄 위치의 번호
arr.sort() # a를 기준으로 정렬
dp = [1 for _ in range(n)]

# i보다 더 이전의 값에서 끝나는 전봇대 = 겹침
for i in range(1,n):
    for j in range(0,i):
        if arr[i][1] > arr[j][1]: # 안 겹친다면
            dp[i] = max(dp[i], dp[j]+1)

# 8-5 = 3
print(n-max(dp)) # 전체개수 - 안겹치는 최대 개수 = 없애야하는 전봇대 최소 개수

            # dp[1] = 1 겹침
            # dp[2] = max(dp[2]=1,dp[0]+1) = 2
            # dp[2] = max(dp[2]=2,dp[1]+1) = 2
            # dp[3] = 1 다겹침
            # dp[4] = max(dp[4]=1,dp[1]+1) = 2
            # dp[4] = max(dp[4]=2,dp[3]+1) = 2
            
            # dp[5] = max(dp[5]=1,dp[1]+1) = 2
            # dp[5] = max(dp[5]=2,dp[3]+1) = 2 
            # dp[5] = max(dp[5]=2,dp[4]+1) = 3
            
            # dp[6] = max(dp[6]=1,dp[1]+1) = 2 
            # dp[6] = max(dp[6]=2,dp[3]+1) = 2 
            # dp[6] = max(dp[6]=2,dp[4]+1) = 3
            # dp[6] = max(dp[6]=3,dp[5]+1) = 4
            
            # dp[7] = max(dp[7]=1,dp[0]+1) = 2
            # dp[7] = max(dp[7]=2,dp[1]+1) = 2
            # dp[7] = max(dp[7]=2,dp[2]+1) = 3
            # dp[7] = max(dp[7]=3,dp[3]+1) = 3
            # dp[7] = max(dp[7]=3,dp[4]+1) = 3
            # dp[7] = max(dp[7]=3,dp[5]+1) = 4
            # dp[7] = max(dp[7]=3,dp[6]+1) = 5

 

 

레퍼런스

• 깃허브 정답

https://github.com/yyeongeun/codingtest/blob/main/BAEKJOON/2565_%EC%A0%84%EA%B9%83%EC%A4%84.py