1. 오늘의 문제
보자마자 최장 증가 부분 수열임을 알아지만 푸는데 꽤나 오랜 시간이 걸렸다.
자꾸 반례에 걸렸는데, 왜 걸리는지조차 알기가 쉽지 않았다.
결국 백준에서 검색을 통해 반례를 찾아보았다.
문제
수열 S가 어떤 수 Sk를 기준으로 S1 < S2 < ... Sk-1 < Sk > Sk+1 > ... SN-1 > SN을 만족한다면, 그 수열을 바이토닉 수열이라고 한다.
예를 들어, {10, 20, 30, 25, 20}과 {10, 20, 30, 40}, {50, 40, 25, 10} 은 바이토닉 수열이지만, {1, 2, 3, 2, 1, 2, 3, 2, 1}과 {10, 20, 30, 40, 20, 30} 은 바이토닉 수열이 아니다.
수열 A가 주어졌을 때, 그 수열의 부분 수열 중 바이토닉 수열이면서 가장 긴 수열의 길이를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000)
2. 반례 모음
6
1 4 3 2 5 1
답 5
10
1 5 2 1 4 3 4 5 2 1
답 7
2
2 1
답 2
6
1 2 3 3 2 1
답 5
10
10 1 3 5 7 6 3 2 1 10
답 8
11
1 2 3 4 5 1 5 4 3 2 1
답 9
3
1 1 1
답 1
3. 코드 구상
처음에는 최장 증가 부분 수열의 최대값을 찾고, 그 인덱스 에서 다시 길이를 측정하는 코드를 짰다.
그렇게 하자 아래 반례에서 문제가 생겼다.
10 / 10 1 3 5 7 6 3 2 1 10
이걸 보자마자 인덱스는 필요 없고, 모든 노드에서 길이를 측정해야 한다는 사실을 깨달았다.
그래서 원래의 배열에서 순차로 길이를 재고, 배열을 뒤집은 다음 순차로 길이를 잰 다음에 두 값을 합쳐주면 될 것 같았다.
4. 코드
from sys import stdin
put = stdin.readline
totalNum = int(put())
# 원래 배열과 길이 배열 준비
numsLst = list(map(int, put().split()))
lengths = [1 for _ in range(totalNum)]
# 뒤집은 배열과 뒤집은 길이 배열 준비
numsLstCopy = numsLst.copy()
numsLstCopy.reverse()
lengthsCopy = lengths.copy()
# 증가 부분 수열 길이 측정
for i in range(0, totalNum):
for j in range(0, i):
if numsLst[i]>numsLst[j]:
thisTotal = lengths[j] + 1
lengths[i] = max(thisTotal, lengths[i])
# 뒤집은 배열의 증가 부분 수열 길이 측정
for i in range(0, totalNum):
for j in range(0, i):
if numsLstCopy[i]>numsLstCopy[j]:
thisTotal = lengthsCopy[j] + 1
lengthsCopy[i] = max(thisTotal, lengthsCopy[i])
# 원래의 배열 순서로 다시 뒤집어 줌
lengthsCopy.reverse()
# 두 값의 합산값들 중 최고 값을 출력함.
results = []
for x, y in zip(lengths, lengthsCopy):
results.append(x+y)
print(max(results)-1)
5. 느낀점
반례가 없으니 오랫동안 헤메었다.
실제 코딩 상황에서도 반례를 알 수 없으니 어떤 상황에서 반례가 나오는지 고민해보는 것도 좋은 공부가 아닐까 생각이 들었다.
이제 LIS는 거의 마스터 한 듯 하다.
