[백준 11053번] 가장 긴 증가하는 부분 수열 파이썬 풀이

가장 긴 증가하는 부분 수열 

1 초

256 MB

155533

62128

41210

37.893%

문제

수열 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의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

예제 입력 1

6
10 20 10 30 20 50

예제 출력 1

4

 

문제의 뜻을 이해 하지 못해 풀이를 참고해서 풀은 문제이다.

따라서 해당 포스팅은 풀이가 아닌 나의 오답 노트이다.

 

우선 다른 분의 풀이를 참고하여 완성한 코드는 다음과 같다.

 

n = int(input())

dp = [0]*(n)  # 원본 배열의 해당 인덱스를 부분 배열의 요소로 삼을것인지 여부를 기록

dp[0] = 1

data = list(map(int, input().split()))

# 입력받은 data의 각 인덱스에서 dp값이 가장 큰 인덱스에 +1을 해주면 된다.

for i in range(1, n):
    for j in range(i):
        # 만족해야 하는 조건
        # 이전의 숫자들이 현재 숫자들보다 작은 숫자일것
        # 이전 숫자들중 가장 큰 값까지 이뤄지는 수열일것
        if data[j] < data[i] and dp[j] > dp[i]:
            dp[i] = dp[j]  # dp값 업데이트
    dp[i] += 1  # 현재 수까지 이어지는 수열을 작성해야 하므로 +1

print(max(dp))  # dp에 기록된 수중 가장 큰 값이 최대 수열의 길이가 됨

 

먼저 수열이라는 것은 "일정한 규칙에 따라 한 줄로 배열된 수의 열" 을 말한다.

따라서 일정한 규칙이 있어야 하며, 해당 문제에서는 수가 계속해서 증가해 나가도록 입력받은 배열에서 수를 선택해야 한다.

 

최대길이수열이 무엇인지에 대해 이해하기 위해 예시로 주어진 숫자들을 토대로 dp테이블을 완성해보자.

dp 테이블의 값에는 해당인덱스까지 완성할수 있는 부분 수열의 최대 길이를 저장한다.

10	20	10	30	20	50
1	2	1	3	1	4

 

dp[0] : 10의 경우 이전에 수가 없으므로 부분순열의 요소로 10을 선택하여 길이가 1이된다.

dp[1] : 20의 경우 20보다 작은 값중 10이 있으므로 10,20이 선택되어 최대 길이는 2가 된다.

dp[2] : 10의 경우 이전 수 중 10보다 작은 수가 없으므로 최대 길이가 1이된다.

dp[3] : 30의 경우 이전 수 중 30보다 작은 값이 존재하고, 그 수들중 dp의 값이 가장 큰 값은 2이므로 dp[1] + 1을 한 값인 30이 답이 된다.

...

 

위와 같은 과정을 통해 최대 길이 수열을 구하는 조건은 아래와 같음을 확인할 수 있다.

 

1. 현재 인덱스의 요소가 이전에 선택된 부분수열의 값보다 큰 수일것

2. 이전 부분수열에서 이어진 수열의 최대길이중 최대 값을 선택할것 => 이후 최대 값에 +1(현재 값도 부분 수열에 포함시켜야 하므로)

 

위의 조건을 입력받은 원본 수열의 0번째 인덱스부터 마지막 인덱스까지 수행하면 문제를 해결할 수 있다.

 

https://www.acmicpc.net/problem/11053

11053번: 가장 긴 증가하는 부분 수열