1. 문제

2565번

2. 코드

• 오답
  - 아래 오답은 '왼쪽 아파트 번호와 오른쪽 아파트 번호가 함께 증가하거나 함께 감소할 때 줄을 끊지 않아도 된다.' 라는 컨셉으로 작성한 코드이다.
  - '한 쌍의 숫자들이 함께 증가하거나 감소하는 최장 수열의 길이를 구한 뒤 N에서 빼면 제거해야하는 전깃줄의 갯수를 알아낼 수 있다'라고 생각 했다. 즉, 바이토닉 컨셉을 적용하려 했다.

N = int(input())
num = [list(map(int, input().split())) for _ in range(N)]

# 두개의 메모이제이션 공간 사용
dp1 = [1 for _ in range(N)] # 정방향 증가 메모이제이션 공간
dp2 = [1 for _ in range(N)] # 역방향 증가 메모이제이션 공간

for i in range(N):
    for j in range(i):
    	# 정방향 증가 최장 순열
        if (num[i][0] > num[j][0]) & (num[i][1] > num[j][1]):
            dp1[i] = max(dp1[i], dp1[j] + 1)
        # 역방향 증가 최장 순열
        if (num[N - 1 - i][0] > num[N - 1 - j][0]) &\
            (num[N - 1 - i][1] > num[N - 1 - j][1]):
            dp2[N - 1 - i] = max(dp2[N - 1 - i], dp2[N - 1 - j] + 1)

dp = [dp1[i] + dp2[i] - 1 for i in range(N)]
print(N - max(dp))

• 처음 접근할 때 생각하지 못한 반례가 있는데, 위 코드에서는 숫자 쌍들이 한번에 증가했다가 감소하는 경우만 생각하고 있는 것이 오류이다. 즉, 감소했다가 증가하는 경우를 생각하지 못했다.

dp1 = [1 for _ in range(N)]
dp2 = [1 for _ in range(N)]

dp3 = [1 for _ in range(N)]
dp4 = [1 for _ in range(N)]

for i in range(N):
    for j in range(i):
        if (num[i][0] > num[j][0]) & (num[i][1] > num[j][1]):
            dp1[i] = max(dp1[i], dp1[j] + 1)
        elif (num[i][0] < num[j][0]) & (num[i][1] < num[j][1]):
            dp3[i] = max(dp3[i], dp3[j] + 1)

        if (num[N - 1 - i][0] > num[N - 1 - j][0]) &\
            (num[N - 1 - i][1] > num[N - 1 - j][1]):
            dp2[N - 1 - i] = max(dp2[N - 1 - i], dp2[N - 1 - j] + 1)    
        elif (num[N - 1 - i][0] < num[N - 1 - j][0]) &\
            (num[N - 1 - i][1] < num[N - 1 - j][1]):
            dp4[N - 1 - i] = max(dp4[N - 1 - i], dp4[N - 1 - j] + 1)


dp090 = [dp1[i] + dp2[i] - 1 for i in range(N)]
dp909 = [dp3[i] + dp4[i] - 1 for i in range(N)]
print(N - max(dp090 + dp909))

• 따라서, 위의 경우처럼 감소했다 증가하는 경우를 고려하기 위해 dp3, dp4를 추가 하였다. 그러나 해당 방식도 오답이다.

• 그렇다! 증가했다가 감소하는 경우(봉우리 형태)와 감소 했다가 증가한느 경우(골짜기 형태) 외에 고려해야 할 형태가 하나 더 있다. 바로 지그재그 형태 이다. 따라서 다음과 같은 숫자가 오면 오답을 출력하게 된다.

9
1 1
9 9
2 2
8 8
3 3
7 7
4 4
6 6
5 5

• 위 값을 입력하면 3을 출력한다. 그러나 교차하는 전깃줄은 없으므로 답은 0이다.

• 사실 위 문제는 왼쪽 아파트의 숫자를 기준으로 오름차순 정렬한 뒤 오른쪽 아파트의 숫자에 대해 최장 증가 수열을 계산하여 훨씬 쉽게 풀 수 있다.

num = sorted(num) # 2중 list에서 sorted function을 적용하면 각 list의 첫번째 요소를 기준으로 정렬한다.

dp = [1 for _ in range(N)]

for i in range(N):
    for j in range(i):
        if num[i][1] > num[j][1]:
            dp[i] = max(dp[i], dp[j] + 1)
            
print(N - max(dp))

• 왼쪽 아파트 숫자와 오른쪽 아파트 숫자 간 정렬 순서에 따라 전깃줄의 교차 여부가 결정된다는 개념을 떠올리고 그것을 문제 풀이에 적용한 것은 나쁘지 않았으나 충분한 경우의 수를 고려하는 습관을 들여야 겠다.