[solved.ac 실버2] 11053_가장 긴 증가하는 부분 수열 (파이썬, DP)

 

제한 사항

 

문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

예제

---

나의 풀이

수열을 순회한다. 현재 10번째 위치에서 가장 긴 증가하는 부분 수열의 길이를 확인하려면 1~9번째 위치까지에서 10번째 위치의 숫자보다 작은 수 중 가장 긴 증가하는 부분 수열을 가진 것 + 1 (10번째 위치)를 하면 된다.

예를 들어 10 20 10 30 20 50 인 수열이 있을 때

4번째에 있는 30을 포함하는 가장 긴 증가하는 부분 수열을 찾으려면 1~3번째에 있는 10 20 10 중 가장 긴 증가하는 부분 수열을 찾으면 된다.

특정 위치의 숫자를 포함하는 가장 긴 증가하는 부분 수열을 저장하는 d 라는 리스트를 만들어 관리했다.

설명이 복잡해보이지만 코드를 보면 쉽게 이해할 수 있을 것이다.

n = int(input())
A = list(map(int, input().split()))
d = [0] * n
for i in range(n):
    for j in range(i): # 현재 위치 미만의 위치에서
        if A[i] > A[j]: # 현재 숫자보다 작은 경우
            d[i] = max(d[i], d[j]) # d 값을 비교하여 갱신
    d[i] += 1 # 현재 위치 값을 포함하도록 1 증가

print(max(d))

 

채점 결과