Part7.5_2_동적프로그래밍(DynamicProgramming)_최대선 연결하기(LIS응용)

문제

1부터 N까지 오름차순으로 나열되어 있다.
서로 선이 겹치지 않고 최대 몇 개의 선을 연결할 수 있는 지 구하라
ex)

입력

첫 줄에 자연수 N(1<=N<=100)이 주어집니다.
두 번째 줄에 1부터 N까지의 자연수 N개의 오른쪽 번호 정보가 주어집니다. 순서는 위쪽번호
부터 아래쪽번호 순으로입니다.

출력

첫 줄에 겹치지 않고 그을 수 있는 최대선의 개수를 출력합니다

풀이

• 오름차순 구했던 DP 문제를 응용한다.
• 이중 for문을 돌려서 가장 긴 오름차순을 구하면 된다.
• res[i] 와 maxLen 을 기록하며 현재 res[i] 과 maxLen를 마지막에 비교하여 최대 길이를 변수에 저장한다.

코드

import sys

sys.stdin=open("input.txt","rt")

def input():
    return sys.stdin.readline().rstrip()

N = int(input())
arr = list(map(int,input().split()))
arr.insert(0,0)
res = [0]*(N+1)
res[1] = 1
maxLen = 0

for i in range(2,N+1): # 마지막 값이 i 라고 생각하고 도는 for문
    max = 0
    for j in range(i-1,0,-1): # i 보다 앞의 값을 비교하는 for문
        if arr[i]>arr[j] and res[j] > max:
            max = res[j]
        res[i] = max + 1
    if res[i] > maxLen: # 최대 수열 초기화
        maxLen = res[i]
print(maxLen)