11053. 가장 긴 증가하는 부분 수열

문제

수열 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

 

---

처음에 이문제는 그냥 중복 제거후 오름차순으로 구현했었다. 
하지만 이 문제의 가장 큰 문제는 증가된 부분 수열이고 이게 이 문제의 가장 큰 힌트였다.

 

즉, 이 문제는

1. 리스트 내 하나의 수를 기준으로 잡고 그 뒤에 나오는 값들을 비교하면서 오름차순으로 증가되는 수열을 찾는 것이다. 그래서 만약 주어진 값이 [5,1,6,2,7,3,8] 이렇게 있으면 

2. '5'을 기준으로 증가된 수열을 찾는다면 [5,6,7,8] 이 나올 것이고, '1'을 기준으로 잡는다면 [1,2,3] 나올 것이다.

3. 하지만 이렇게 구현한다면 단점이 생긴다.

만약 주어진 값이 [1,3,4,2,3,4] 일 경우 '1'을 기준으로 잡는다면 [1,3,4] 와 [1,2,3,4]가 나올 것이다.  

4. 그래서 이 문제는 DP를 사용해서 풀어야 겠다고 생각을 했고 DP문제는 거의 max(), min()이 나오기 때문에 코드를 작성했다.

-> DP문제는 이전에 계산된 값을 재사용해서 해결하는 방식이고 나는 상향식 접근법을 이용해 for문으로 구현했다. 그러기 위해서는 결과를 저장하는 TABLE이 필요하다. 이걸 나는 dp라는 리스트를 만들었다. 

5. 기준을 잡은 숫자와 그 이전의 숫자의 DP 배열의 값을 비교하여 문제를 풀면된다.

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

dp = [0] * n 
for i in range(n):
    for j in range(i):
        if a[i] > a[j] and dp[i] < dp[j]:
            dp[i] = dp[j]
    dp[i] += 1

print(max(dp))

 

코드 설명

입력값 : n = 6

입력값 : a = [10, 20, 10, 30, 20, 50]

dp = 초기값 : [0, 0, 0, 0, 0, 0, 0]

        for문을 다 돌고 난 뒤 : [1, 2, 1, 3, 2, 4]

 

1. dp 라는 이름의 리스트를 만들고 0으로 초기화를 한다. => dp = [0,0,0,0,0,0]

2. 첫번째 for문으러 값을 지정해준다 .

3. 두번째 for문으로 지정한 값을 이전값들과 비교해준다.

4. if 문에서 a[i] > a[j]는 지정한 값이 이전 값보다 커야하고 dp[i] < dp[j]는 현재 값이 이전 값보다 작으면 현재 dp리스트에 이전 dp 값을 지정한다.

5. for문이 다 돌면 dp[i]에는 0 또는 i 이전의 j 중 dp 값이 큰 dp[j]의 값이 들어 있을 것이다.

6. 그리고 dp[i]에 1을 더해주고 

7. dp값중 가장 큰 값을 출력해준다.

 

3번 과정의 자새한 풀이

# i = 0일 때 , a[0] = 10, dp = [1, 0, 0, 0, 0, 0]
# i = 1 , a[1] = 20, a[1] > a[0] 이고 dp[1] < dp[0] 이므로 dp = [1, 2, 0, 0, 0, 0]
# i = 2 , a[2] = 10, a[2] > a[0] 은 거짓이므로 dp = [1, 2, 1, 0, 0, 0]

# i = 3,

.

.

.

 

이렇게 풀면 결국에 dp =  [1, 2, 1, 3, 2, 4이 남게 될 것이고 이 중 가장 큰 값을 출력해주면 된다.