[인프런] 최대 선 연결하기

---

문제설명

왼쪽의 번호와 오른쪽의 번호가 있는 그림에서 같은 번호끼리 선으로 연결하려고 한다. 왼쪽번호는 무조건 위에서부터 차례로 1부터 N까지 오름차순으로 나열되어 있다. 오른쪽의 번호 정보가 위부터 아래 순서로 주어지면 서로 선이 겹치지 않고 최대 몇 개의 선을 연결할 수 있는지 구하라

 

 

위 그림은 오른쪽 번호 정보가 4, 1, 2, 3, 9, 8. 5, 6, 10, 8로 입력되었을 때 선이 서로 겹치지 않고 연결할 수 있는 최대 선을 개수 6으로 구한 경우이다.

입력조건

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

출력조건

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

사고과정

• 문제에서 증가하는 부분수열 최대길이를 구하는 유형이라는 것을 잘 파악해야 했던 문제이다. 증가하는 부분수열 최대길이를 구하라는 것을 다른 텍스트로 마치 연막쳐놓은 듯 한 문제였다..

풀이

n = int(input())
arr = list(map(int, input().split()))
dp = [1] * n
answer = 0
for i in range(1, n):
    for j in range(i-1, -1, -1):
        if arr[j] < arr[i]:
            dp[i] = max(dp[i], dp[j] + 1)
    answer = max(answer, dp[i])

print(answer)