11054 가장 긴 바이토닉 부분 수열
쉽게 생각하면, 11053의 LIS를 두번 적용하는 것 뿐인 문제였다. 바이토닉 부분 수열이라는 것이, 특정 element를 기점으로 쭉 증가하다가 감소하는 형태를 보이는 수열인데, 이것은 가장 긴 증가하는 부분수열과 가장 긴 감소하는 부분수열의 합쳐진 형태였기 때문이다. 가장 긴 감소하는 부분수열 문제도 있었기에 그것을 그대로 인용해도 됐지만 가장 긴 감소하는 부분수열이라는 것이 다르게 생각하면 마지막에서부터 거꾸로 올라간다면 그것도 역시 거꾸로 가장 긴 증가하는 부분수열이었기 때문에 결국 LIS를 2번 적용하되 하나는 거꾸로 적용하면 되는 형태였다.
따라서 증가하는 부분수열 increase, 감소하는 부분수열 decrease를 선언해놓고 두개를 합칠 예정인 result를 놓고 시작한다. 이때 이중for문을 2개 써서 increase와 decrease를 채워주는데 이 형태는 11053 LIS 문제의 코드와 완전히 동일하다. 다만 decrease를 할 때는 for문을 n-1부터 시작하여 -1씩 거꾸로 올라가는 형태로 설정해주었다. result로 각각의 원소에 대한 dp값을 합쳐줬는데, 이때 주의할 것은 "특정 원소"를 기점으로 증감이 이루어지는 형태가 바이토닉이었기 때문에 특정 원소가 2번 들어가 중복되게 된다. 그렇게 때문에 개수를 1개 빼주고, result에서 max를 찾으면 이것이 곧 가장 길게 증가하고 가장 길게 감소하는 형태인 바이토닉이 된다.
참고로 다른 방법은 처음부터 lst의 역순인 리스트를 하나 만들어 주는 것이었다. 예를 들어 lst_reverse = lst[::-1]로 해주고 완전 동일한 코드에서 lst를 lst_reverse로 써주면 되는데 이것은 lst의 마지막 원소를 첫번째 원소로 두고 거꾸로 올라가는 형태를 정방향으로 그냥 넣어준 것일 뿐이다. 쉽게 말해 lst를 역순으로 정렬해준 것이다. 그렇게 되면 lst_reverse에서 LIS를 적용해도 그것이 자연스럽게 가장 긴 감소하는 부분수열의 형태가 되기 때문이다.
# 11054 가장 긴 바이토닉 부분 수열
import sys
input = sys.stdin.readline
n = int(input())
lst = list(map(int, input().split()))
increase = [1] * n
decrease = [1] * n
result = [0] * n # increase + decrease
# 증가부분, 감소부분은 11053의 처음 LIS 문제랑 코드가 완전 동일
# 증가 ( -> 방향)
for i in range(n):
for j in range(i):
if lst[i] > lst[j]:
increase[i] = max(increase[i], increase[j] + 1)
# 감소 ( <- 방향 )
for i in range(n - 1, -1, -1):
for j in range(i + 1, n):
if lst[i] > lst[j]:
decrease[i] = max(decrease[i], decrease[j] + 1)
# result 구하기
for i in range(n):
result[i] = decrease[i] + increase[i] - 1 # -> 방향, <- 방향 가면서 cross 되는 부분이 겹치니까 1 빼줘야함
print(max(result))
2565 전깃줄
list를 입력받는 두번째 줄이 극한으로 줄어들어서 한줄로 처리할 수도 있다는 점이 인상깊었다. 기본적인 맥락은 LIS였지만, 핵심은 sort를 하는 부분이었다. A전깃줄이나 B전깃줄 둘중에 하나만 sort해도 되는데, sort하는 이유를 좀 생각해보았다.
내가 생각한 sort 이유는 겹치지 않게 하기 위함이었다. 전깃줄이 서로 겹치지 않으려면 반드시 증가하는 형태로 A와 B가 매칭이 되어야 했다. 1번 전깃줄이 만약 9번 전깃줄과 이어진다면 남은 전깃줄들이 겹치지 않기 위해선 10번 전깃줄 밖에 없기 때문에, 가장 많은 전깃줄이 들어가기 위해선 최대한 1번과 가까운 전깃줄부터 시작하여 최대한 많은 전깃줄을 담아야했고 이것이 바로 LIS의 맥락과 동일했다.
따라서 A를 정렬하고 B에 대해 LIS를 적용해도 되고, 어차피 A와 B는 연결되어있기 때문에 B를 정렬하고 A에 대해 LIS를 정렬해도 된다.
정렬하는 이유가 아주 말끔하게 이해된 것은 아니라 나중에 이해되면 다시 추가해보아야겠다...
# 2565 전깃줄
n = int(input())
a = sorted([list(map(int, input().split())) for _ in range(n)])
# 가장 긴 증가하는 수열을 만들면, 이 말이 곧 가장 많은 전깃줄을 가지고 있다는 뜻이므로
# 가장 긴 증가하는 수열의 길이를 전체 개수에서 빼면
# 문제에서 구하라는 없애야하는 전깃줄의 최소 개수를 구하게 된다.
dp = [1] * n
for i in range(n):
for j in range(i):
if a[i][1] > a[j][1]:
dp[i] = max(dp[i], dp[j] + 1)
print(n - max(dp))
