[BOJ] 2565 전깃줄 Python

DP 문제라고 한다..

근데 이해가 안되서 일단 외우려고 적는 중

 

정답 풀이법은 다음과 같다.

1) sort로 일단 정렬

2) dp 배열을 만들어주고, 첫 for문은 1,T까지, 두번째 for문은 첫번째 for문 인자값까지 돌려준다.

3) sort로 정렬해줬으니 무조건 [0]값은 순서대로 일 것이므로, 비교는 [1]값만 해주고,

4) dp 첫번째 인자값이 dp 두번째 for문 인자값 + 1 보다 작으면 

dp 첫번째 인자값을 늘려준다 두번째 인자값 + 1로 늘려준다....

근데 진짜 먼소리인지 모르겠다.

 

 

*** 배열은 되도록이면 append 하지 말고 미리 크기 만큼 선언, 초기화해놓고 값을 변경해주자

 

T = int(input())

mt = [[0,0] for _ in range(T)]

for i in range(T):
    a, b = map(int, input().split())
    mt[i][0] = a
    mt[i][1] = b

mt.sort(key = lambda x:x[0])
    
print(mt)

lis = [1]*T
for i in range(1, T):
    for j in range(i):
        if mt[i][1] > mt[j][1] and lis[i] < lis[j]+1:
            lis[i] =lis[j] + 1

print(T-max(lis))

 

참고

[백준알고리즘] 1931번: 회의실배정 -Python