백준 2565 - 전깃줄

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

2565번: 전깃줄

 

 

이 문제는 전봇대 A에서 전봇대 B로 여러 전깃줄을 설치할건데, 모든 전깃줄이 겹치지 않기 위해서 제거해야 할 전기줄의 최소 갯수를 구하는 문제이다.

 

 

거의 1시간 들여서 코드 작성을 했는데, 9퍼센트에서 오답이 나왔는데, 어디에서 틀린건지는 아직도 모르겠다..

 

 

오답코드)

n = int(input())
line = []
for i in range(n):
    line.append(list(map(int, input().split())))

flag = 0
dp = [0] * n
# 겹치는 갯수를 세는 반복문
for i in range(n):
    flag = 0
    if line[i][0]>line[i][1]:  # A가 더 위에 있을 경우
        flag = -1
    for j in range(i+1, n):
        if flag == 0:
            if line[j][1] < line[i][1] and line[j][0] > line[i][0]:
                dp[i] += 1
                dp[j] += 1
        else:
            if line[j][0] < line[i][0] and line[j][1] > line[i][1]:
                dp[i] += 1
                dp[j] += 1

cnt = 0
tmp = 0

dp.sort() # 겹치는 횟수 정렬
s = sum(dp) # 모든 합을 구함

if s!=0: # 만약 합이 0이 아니면
    while True:
        tmp = dp[-1] # 가장 많이 겹치는 횟수
        s = s - 2*tmp # 전기줄을 제거 할 것이므로 겹치는 횟수 * 2를 전체 횟수에서 차감
        dp.pop() # 가장 많이 겹치는 전기줄 제거
        cnt +=1 # 제거 횟수 1 증가
        if s<=0: # 전체 합이 0보다 작거나 같아질 경우
            break # 반복문 탈출

print(cnt)

위 오답코드는 전의 값을 이용해서 푼 것은 아니니 dp가 아닌 것 같다.

어쨋든 로직을 살펴보자면,

 

가장 많이 겹치는 전깃줄을 구해서 제거하는 알고리즘이다.

반복문을 통해 각 전깃줄마다 겹치는 횟수를 구했다.

 

가장 많이 겹치는 전깃줄을 제거할건데 pop으로 간편하게 제거하려고

아래에서 겹쳐지는 횟수가 들어간 리스트를 정렬했다.

 

최종 목적은, 하나도 안 겹쳐지게 만들기 위해 빼야될 최소 전깃줄의 갯수를 구하는 것이므로

겹쳐지는 횟수의 모든 합을 구한 뒤, 전깃줄을 빼주고 해당 합도 차감을 하며 

최종적으로 전체 횟수의 합을 0으로 만드는 것이 목표였다.

겹쳐지는 횟수를 모두 더한 값이 0이어야 하나도 안겹쳐진다는 뜻이기 때문이다.

 

여기서 주의할 점은, 합에서 차감하는 알고리즘이다.

전체 합이 s, 차감할 전깃줄의 겹쳐지는 횟수를 tmp라고 하자.

 

그럼 전체 합 s에서 tmp를 뺄 것이 아니라, tmp*2한 값을 빼주어야 한다.

그 이유는, 일단 전깃줄를 제거할거니 해당 전깃줄의 겹쳐지는 횟수를 빼는건 당연하고

해당 전깃줄이 겹쳐지는 횟수를 카운트할 때 이중 카운트되기 때문이다.

(a, b가 겹쳐진다고 하면 a의 횟수도 1, b의 횟수도 1 => 따라서 둘 다 빼주어야 함)

 

정렬 결과, 맨 마지막에 최대값이 위치하게 되고 while문을 돌면서 계속 빼주게 구현했다.

조건은 모든 횟수의 합이 0이 될 때까지...

 

이렇게 작성하면 겹쳐지는 횟수가 최대값인 전봇대가 중복이 되어도 ㄱㅊ다고 생각했다. 

 

결론적으로는, 틀렸다.. 나중에 뭐 다시 생각해보던가..다시 질문해봐야겠다.

 

그래서 구글링을 했고 예상치도 못한 해결방법에 놀랐다.

구글링한 결과, DP에서 계속 다뤄왔던 LIS(최장 부분 증가 수열)을 이용했기 때문이다.

 

참고한 포스팅은 이거다.

https://myjamong.tistory.com/316

 

 

 

일단, 풀이코드는 다음과 같다.

 

풀이코드)

n = int(input())
line = []
dp = [1] * n
for i in range(n):
    line.append(list(map(int, input().split())))

line.sort(key=lambda x: x[0])
seq = [x[1] for x in line]

for i in range(n):
    for j in range(i):
        if seq[i] > seq[j]:
            dp[i] = max(dp[i], dp[j]+1)

print(n - max(dp))

위 코드에서 중요한 알고리즘을 정리해보도록 하겠다.

그러기 위해서는, 해당 문제를 풀기 위해 어떻게 접근해야 할지 먼저 생각해보자.

 

이 문제에서 최종적으로 구해야 할 것은, 제거해야할 전깃줄의 최소 갯수이다.

최소로 제거한다는 것은, 겹치지 않는 전깃줄의 갯수가 최대로 남아 있어야 한다는 것이다.

 

서로 전깃줄이 교차하지 않기 위해서는, 도착하는 전봇대의 번호가 연속적으로 증가해야 한다.

 

따라서, 

출발 지점을 순서대로 나열한 뒤, 도착하는 전봇대의 번호를 기준으로  LIS를 적용하면 된다. 

 

• 정렬 사용
  • 출발 지점 정렬하여야 그 순서에 따른 도착 지점의 번호를 알 수 있다.
  • line.sort(key = lambda x: x[0])
  • 정렬된 리스트에서 두 번째 원소인 도착 번호만 가져옴
• LIS
  • 구한 도착 번호를 기준으로 증가 부분 수열의 최대 길이를 구함
• 최종 답 도출
  • 증가 부분 수열의 최대 길이는 겹치지 않는 전깃줄의 최대 갯수와 같다.
  • 전체 전깃줄의 갯수 n - 겹치지 않는 전깃줄의 최대 갯수 = 제거해야 할 전깃줄의 최소 갯수

 

 

 

생각도 못했는데 LIS라니 놀랍다..쩝