백준 전깃줄 파이썬

같은 배열들 사이가 줄로 연결되는것이기때문에 

6 - 6 3-3 이런식으로 연결되는게 가장 이상적인조합이다 동일번호로 연결될시 최대한 많은 전깃줄을 연결할수있다

반대로 1-10 9-2 처럼 극단적으로 차이가 많이나는경우는 제거될 확률이 높아진다

 

그렇다면 많이 차이가 나는 경우를 지우면 될까? 아니다 반례가있다

 

전깃줄이 있다 서로 겹치는 상황이다

각 전깃줄마다 다른 전깃줄과 겹치는 부분을 모두 세본다

 

가장 많이 겹치는 순서대로 하나씩 지워본다 더이상 겹치는 전깃줄이 존재하지 않을때까지

이렇게 하는게 최고의 방법일까?

 

예제에서 각 전깃줄당 다른 전깃줄과 겹쳐지는 수를 구해보자

5 2 4 3 2 2 2 0 많이겹친 탑3를 제거하자 겹치는 전깃줄이 없어졌다

 

그리고 남은 전깃줄들의  숫자가 똑같았다 이것도 제거의 기준이 될수있을까?

반럐를 찾았따 제거의 기준이 될수없다

 

그나저나 어쨋든 DP문제이기때문에 DP로  풀수있는방법이 있는지 생각해보자

 

DP방식으로 푸는 방법은 머리속에 쉽게 어떻게 해야할지 잘 떠오르지않는것같다

 

따라서 처음의 아이디어로 먼저 구현해본다

 

나보다 위에 있는데 다른전봇대에서는 나보다 낮으면 겹친것이다 

나보다 아래에 있는데 다른전봇대에서는 나보다 높으면 겹친것이다

 

이를 판별하는 두개의 함수를 만든다

 

저함수에 해당한수만큼 다른줄과 꼬인것이다

 

이렇게 모든 줄에대하여 다른 전깃줄과 겹쳐진 횟수를 구하고 

 

가장 겹쳐진게 많은 전깃줄을 지우고 다시한번 구하고 겹쳐진게 있으면

또 그중에서 가장 겹쳐진수가 많은 전기줄을지우고.... (반복)

 

그러면 반복횟수가 너무많다...

그게 이방법의 문제점인것같다

그리고 위에서도 말했다싶이 겹쳐진수가 일정한것들을 지우지않아도될 전깃줄로 보는것이 적용되지않는 사례도 있다

 

모든 요소의 겹치는 숫자를 모두 알아낸다

거기서 가장 겹치는 숫자가 많은 라인을 제거한다 또 다른라인에서 해당 숫자를 지운다

아직 겹치는 숫자가 있다면 위의 과정을 반복한다

 

겹치는경우가 생기면 둘중에 하나는 없어져야함

 

모르겠다 답을 봐야겠다 ㅠ

출처

오름차순으로 만든후 저번에 부분수열 만들때 최대 증가 수열을 구했다면

이번엔 가장 많이 이어지게 만드는게 포인트 가장긴 부분수열

 

접근방식이 어떻게 하면 최소로 제거할까가 아닌 어떻게 하면 최대로 연결할수있을까이다 

난 한번도 이런식으로 접근해본적없다

굳이 오름차순으로 정리한것은 계산을 더쉽게 하기위함인것같다

 

제출

N=int(input())
z=[]
d=[1 for i in range(N)] #dp리스트
for i in range(N): # 입력값 모두 받기
    a,b=map(int,input().split())
    z.append([a,b])

z.sort() #정렬
# print(z)
# print(d)
for i in range(N):
    p=[0]
    for j in range(i):
        if z[i][1]>z[j][1]:
            p.append(d[j])
    d[i]=max(p)+1

print(N-max(d))

정답

나는 dp값을 갱신시킬때 max()를 이용했는데, p가 빈리스트일경우 에러가 발생하게된다

이분은 max함수를 이용하지않고 dp[i]의 최대값을 갱신시키는 방식으로 진행하셨는데

 

훨씬 깔끔하다고 느꼈다

 

최소한으로 구하는건 다른쪽에서의 최대가 될수있다

조건을 만족시키는 최대한의 방법을 구할때는 LIS

후 너무 공식적으로 접근하는건가.. 어렵다!