[백준/python] 11055번 가장 큰 증가 부분 수열

1. 문제

 

증가 부분 수열이란,

수열의 부분 수열 중 증가하는 값으로만 이루어진 수열이다.

단, 수열의 순서를 바꾸어서는 안 된다.

그 중 합이 가장 큰 것을 구하는 문제이다.

2. 풀이

[접근 1]

처음에는 dfs를 생각해서 문제를 풀었다.

 

1. 처음 값을 더해준다.

2. 해당 값 보다 뒤에 있는 숫자들에 대해 그 값이 더 클 경우 dfs를 실행한다.

3. dfs 실행을 마치고나면 기존 결과와 현재까지의 합계 중 큰 값을 결과값으로 바꾼다.

4. 값이 더 작은 경우에는 넘어간다.

 

코드 작성은 잘 하였고 답에는 이상이 없어서 채점을 했는데 결과는 실패..

시간 초과가 떠버렸다.

그래서 접근 방법을 바꾸었다.

 

[접근 2]

이번에는 dp를 활용해서 문제를 풀었다.

dp 테이블을 만들어서 각각 인덱스까지의 최대 합을 구한 뒤 그 중 최댓값을 출력하는 방식.

첫 번째 인덱스만 미리 초기화를 해두고 2~n 번째까지는 반복문을 돌려서 max를 구했다.

 

예를 들어 현재 수열이 [1, 2, 3, 4, 5]이고 인덱스가 3인 경우에,

수열의 0, 1, 2 번째 값에 대해 비교를 수행하며 max 값을 갱신한다.

현재 인덱스의 값, A[3] = 4이고 이 값이 A[0] = 1 보다 크기 때문에

기존 값(0) vs 0까지의 값(1) + 현재 인덱스의 값(3)

비교를 통해 dp테이블의 3번 인덱스의 값을 최댓값으로 변경해준다.

 

3. 코드

[접근 1]

def dfs(v):
    global sum, result
    sum += A[v] #합계에 현재값 더해주기
    #v보다 크거나 같은 수에 대해 dfs 실행
    for i in range(v+1, n):
        if A[v] <= A[i]:
            dfs(i)
            result= max(result, sum) #최대로 결과값 설정
            sum = A[v] #합계를 이전 결과로 초기화
    
#입력
n = int(input())
A = list(map(int, input().split()))
sum = 0 #합계 초기화
result = 0 #결과값 초기화

dfs(0)
print(result)

 

[접근 2]

import sys
input = sys.stdin.readline

#입력
n = int(input())
A = list(map(int, input().split()))
d = [0] * n #dp 초기화
d[0] = A[0] #첫 번째까지의 합
#2~n번째까지 각각 합계 max 구하기
for i in range(1, n):
    #현재 인덱스까지 모든 수 확인
    for j in range(i):
        #현재 인덱스의 값이 큰 경우 j를 더했을 때와 비교하여 max값 갱신
        if A[j] < A[i]: 
            d[i] = max(d[i], d[j]+A[i])
        #아닌 경우는 j를 더하지 않고 max값 갱신
        else:
            d[i] = max(d[i], A[i])
#출력
print(max(d))

4. 결과

 

 

알고리즘을 어떤 상황에서 써야 하는지 좀 더 명확한 정리가 필요할 것 같다.

dfs, bfs, dp에 대해 다시 한 번 정리해야겠다.