백준 11055 가장 큰 증가 부분 수열 파이썬

www.acmicpc.net/problem/11055

11055번: 가장 큰 증가 부분 수열

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

for i in range(1, n):
    dp[i] = nums[i]
    if nums[i] > nums[i - 1]:
        dp[i] = nums[i - 1] + nums[i]

    for j in range(i - 1, -1, -1):
        if nums[i] > nums[j]:
            dp[i] = max(dp[i], nums[i] + dp[j])

print(max(dp))

 

DP로 넘어와서 상당히 많이 좌절하고 있다.

제대로 푼 문제가 잘 없을 정도.. 

그나마 최근들어 한두문제씩 스스로 풀고있다.

DP를 풀어보면서 느낀점은 

문제를 풀어나가는 규칙을 찾아야하는데 

규칙을 찾는 과정에서 재귀적 사고를 해야하고, 큰문제를 작은 부분문제로 나눌줄 알아야하며

작은 부분문제에서 어떤걸 저장해놨다가 다음 단계의 문제를 풀때 불러서 써야할지를 생각하고

DP테이블에 초기값을 저장하기 위해, 낮은 단계는 직접 한땀한땀 경우의수를 대입해보면 좋다는것이다.

 

결국 위 과정을 거치고 골똘히 생각하다보면 규칙이 보이고 점화식을 세울수 있게 된다.. 인데 아직 나도 잘 안된다.

지금까지 공부한 그리디, DFS,BFS, 정렬등과는 전혀 다른느낌..

anyway..

 

이 문제는 dp table 에 입력받은 값과 동일한 값이 초기값이며

i를 증가하면서 이전 값 보다 크면 증가하는 부분 수열이므로 nums[i] 와 nums[i-1] 을 합한 값을 dp 테이블에 저장해준다.

그 다음 현재 i에서 0번째까지 역주행하면서 이전 값이 현재 값보다 작은 경우 (이 경우 증가하는 수열이므로)

현재 dp테이블에 누적된 값과 현재 값과 이전에 dp 테이블에 누적된 값중 최대값을 구한다.

 

이 문제는 오랜만에 아무것도 참고하지 않고 풀었는데, 글로 풀어쓰려니 또 쉽지가 않다.