[BOJ] 11053 - 가장 긴 증가하는 부분 수열

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

예제 입력

6
10 20 10 30 20 50

예제 출력

4

문제 해결

이 문제에서 주목해야할 점은 수가 크게 커지는게 중요한 것이 아니라 많이 커지는 것이 중요하다. 따라서 입력을 받는 arr 과 그 단계까지의 최대 값을 담는 dp 배열을 만들어 보자

index	0	1	2	3	4	5
arr	10	20	10	30	20	50
dp	0	0	0	0	0	0

index가 0일 경우
index가 0인 경우는 1 증가이므로 dp[1] 에 1을 넣는다.

if i == 0 :
    dp[i] = 1

index가 1 이상인 경우
index가 1 이상인 경우는 index 이전 까지의 배열 중 arr[i] 보다는 작으면서 가장 큰 dp 값을 찾는다. 우선 수가 상승해야 하므로 전의 숫자가 작아야 한다. 그리고 가장 많은 상승폭을 얻어야 하기 때문에 dp값도 가장 커야 한다.

1. arr[j] < arr[i]
2. dp[j] 가 가장 큰수

위의 조건에 맞는 코드는

else :
    max_dp = 0
    for j in range(0, i)
        if max_dp < dp[j] and answer[j] < answer[i]:
            max_dp = dp[j]
    dp[i] = max_dp+1

이제 코드로 옮겨 보자.

python 코드

n = int(input())
answer = list(map(int, input().split()))
dp = [0] * n

for i in range(0, n):
    if i == 0 :
        dp[i] = 1
    else :
        max_dp = 0
        for j in range(0, i):
            if max_dp < dp[j] and answer[j] < answer[i]:
                max_dp = dp[j]
        dp[i] = max_dp+1

print(max(dp))

Test Case

8
18 48 82 70 18 16 91 26
current answer :  4
-----------------------
9
67 29 43 111 69 5 14 77 131
current answer :  5
-----------------------
14
34 33 26 66 109 72 135 19 117 107 128 62 92 147
current answer :  6
-----------------------
6
94 76 35 74 133 94
current answer :  3
-----------------------
9
111 42 146 16 26 43 81 144 76
current answer :  5
-----------------------
15
15 39 86 105 23 149 113 124 140 46 29 150 38 133 19
current answer :  8
-----------------------
15
21 105 89 82 84 73 35 57 7 127 28 120 32 31 146
current answer :  5
-----------------------
10
91 86 59 22 134 90 104 141 147 101
current answer :  5
-----------------------
14
118 126 103 50 25 85 72 58 61 150 146 59 137 38
current answer :  4
-----------------------
3
3 74 93
current answer :  3
-----------------------

느낀점

BFS, DFS 문제는 못 풀것 같고 DP 문제 위주로 해결해보겠다.