[DP] boj 11053, 11054, 11055, 11722 - 가장 긴 증가하는 부분 수열(LIS)

백준 11053, 11054, 11055, 11722 문제는 LIS(Longest Increasing Subsequence) 유형이다.

11053

숫자 범위 전체를 배열로 만들고 slicing을 사용하는 방법이 있다. 참고 링크

이분탐색으로도 가능하다. 참고 링크

지금 찝은(i) 기준 원소의 좌측에서 보다 작은 값이 있는지 찾고, 그 작은 값이 갖고 있는 증가 수열의 최대값을 가져옴.
좌측의 원소를 다 검사해서(for j in range(i)) 그 중 유효(원소 값이 기준 원소보다 작은)하면서 가장 긴 증가 수열의 길이(tempMax)를 가져오고, 1을 추가해 지금 기준 원소 포함, 이걸 끝으로 하는 증가 수열의 최대 길이를 저장한다.
증가 수열의 최대 길이만 저장해둔 tempArr에서 가장 큰 값을 정답으로 return한다.

import sys

n = int(sys.stdin.readline())
inputArr = list(map(int, sys.stdin.readline().split(' ')))

tempArr = [1 for _ in range(n+1)]  # 수열 원소의 최소값 1
# 해당 index의 inputArr값이 갖는 증가 수열의 최대 길이를 저장

for i in range(1, n):   # 내부 for문을 실행하기 위해 1부터 시작
    tempMax = 0
    for j in range(i):
        if inputArr[j] < inputArr[i] and tempArr[j] > tempMax:
            tempMax = tempArr[j]
    tempArr[i] = tempMax + 1    # 자신(inputArr[i])도 포함한 길이로 증가수열의 최대 길이를 넣어줌

print(max(tempArr))

 

---

11054

증가 수열과 감소 수열을 나눠서 index별 최대 길이를 각기 구했다. 그리고 두 배열을 합칠 때 operator.add와 map을 사용했다. map의 type param이 들어가는 자리에 method도 가능하다는 걸 알았다.

import sys
from operator import add

n = int(sys.stdin.readline())
inputArr = list(map(int, sys.stdin.readline().split(' ')))
ascArr = [1 for _ in range(n)]  # 증가 수열의 길이를 저장할 배열
descArr = [1 for _ in range(n)] # 감소 수열의 길이를 저장할 배열

# 증가 수열
for i in range(1, n):
    tempMax = 0
    for j in range(i):
        if inputArr[j] < inputArr[i] and ascArr[j] > tempMax:
            tempMax = ascArr[j]
    ascArr[i] = tempMax + 1 # 자신(inputArr[i])도 포함하기 위해 +1

# 감소 수열
for i in range(n-1, -1, -1):    # 오른쪽에서 왼쪽으로 가면서 기준의 우측을 확인
    tempMax = 0
    for j in range(i+1, n):
        if inputArr[j] < inputArr[i] and descArr[j] > tempMax:
            tempMax = descArr[j]
    descArr[i] = tempMax + 1

result = list(map(add, ascArr, descArr))
print((max(result)) - 1)    # 기준(가장 큰 수)이 중복으로 더해졌으니 -1

---

11055

11053과 같은 방식. 합이기 때문에 index마다의 최대 합을 저장해두는 배열과 inputArr[0] 처리에 유의해야 된다.

import sys

n = int(sys.stdin.readline())
inputArr = list(map(int, sys.stdin.readline().split(' ')))

sumArr = [0 for _ in range(n)]  # 증가 부분 수열의 합
sumArr[0] = inputArr[0]    # index가 0일 때 자기 자신을 합으로 넣어둠
# 이게 없으면 이 원소가 들어가는 모든 합에서 이 값이 빠진 상태로 나옴

for i in range(1, n):   # 내부 for문을 실행하기 위해 1부터 시작
    tempMax = 0
    for j in range(i):
        if inputArr[j] < inputArr[i] and sumArr[j] >= tempMax:
            tempMax = sumArr[j]
    sumArr[i] = tempMax + inputArr[i]

print(max(sumArr))

---

11722

11053과 같은 방식에서 for문에서 탐색하는 방향만 바꿔 감소 수열 길이를 구함.

import sys

n = int(sys.stdin.readline())
inputArr = list(map(int, sys.stdin.readline().split(' ')))
tempArr = [1] * n

for i in range(n-1, -1, -1):
    tempMax = 0
    for j in range(i+1, n):
        if inputArr[j] < inputArr[i] and tempArr[j] > tempMax:
            tempMax = tempArr[j]
    tempArr[i] = tempMax + 1

print(max(tempArr))