다리 건설

1. 문제

강의 상부와 하부를 연결하는 다리를 건설해야한다. 다리는 여러 지점으로 나눠져있고, 같은 번호의 지점끼리만 연결할 수 있다.

1. 다리를 건설하기 위해 미리 N개의 지점을 골라두었다.
2. 강 한쪽은 1번부터 N번까지 순서대로 지점에 번호를 매겼지만 반대쪽은 무작위로 매겨져 있다.
3. 같은 번호의 두 지점끼리만 다리로 연결할 수 있다.
4. 두 개의 다리는 겹칠 수(교차될 수) 없다.
5. 주민들의 편의를 위해 다리는 최대한 많은 개수를 건설하고자 한다.

2. 입력

첫 번째 줄에는 지점의 개수 N이 주어진다. (5 <= N <= 1000)

두 번째 줄에는 각 지점의 번호 ai가 주어진다. (1 <= ai <= N)

지점의 번호는 중복되지 않는다.

3. 출력

건설할 수 있는 최대 다리 개수를 출력한다.

4. 알고리즘 : 동적계획법

 여기서 주목할 것은 강 상부의 다리 번호는 오름차순으로 되어있다는 것이다. 하지만 다리를 연결할 때는 교차될 수 없으므로 강 하부의 다리번호 또한 순서대로 되어야한다는 것이다. 따라서 이 문제는 다음과 같이 바꿀 수 있다.

---

주어진 무작위의 번호에서 가장 긴 오름차순 부분 수열의 길이를 찾아라

---

이제 문제를 위와 같이 정의했다면, 이제 두 단계로 나눌 수 있다.

1. 첫 번째부터 N-1번째까지 원소가 있을 때의 가장 긴 부분수열(Longest Increasing Subsequence, LIS)에서
2. 가장 긴 부분수열의 가장 마지막 원소보다 N번째 원소가 큰지, 작은지 비교하여 최종 답을 도출한다.

 

5. 소스코드

n = int(input())
bridge = list(map(int, input().split()))

dp = [1 for _ in range(n)] # 각 지점에서의 가장 긴 부분수열의 길이를 저장하는 리스트

for i in range(n):
    for j in range(i):
        if bridge[i] > bridge[j]:
            dp[i] = max(dp[i], dp[j] + 1)

print(max(dp))