문제 출처 : https://www.acmicpc.net/problem/11052

사고과정

다이나믹 프로그래밍이라는 걸 알기 때문에 해결할 수 있었던 것 같은데... 백퍼센트는 아니고 그냥 팁이라면 팁으로 알고 있자면 일차원적인 최댓값 문제는 DP, 그리디 알고리즘으로 주로 풀린다.

문제는 심플!

import sys

N = int(sys.stdin.readline().rstrip("\n"))
card = [0]+list(map(int,sys.stdin.readline().rstrip("\n").split()))
cost = [0 for _ in range(N+1)]

for n in range(1,N+1) :
    cost[n]= max([cost[n-i]+card[i] for i in range(0,n+1)])
print(cost[n])

하지만 시간복잡도가 O(n^2)이라 좀 더 효율적인 풀이방식이 있지는 않을까 고민했지만 다른 사람들의 풀이를 보니 이 방식이 상당히 빠른 축에 속하는 것 같기에 더 이상의 고민은 생략한다.

항상 "빅오는 어떻게 되며 어떻게 하면 더 효율적으로 짤 수 있을까" 고민한다. 어떤 것은 O(n^2)이 정답이 되고 어떤 것은 O(n)이 정답이 되기에 이를 분별하고 판단하는 능력을 함양할 필요성을 뼈저리게 느낀다.

그런 의미에서 유사한 느낌을 받으라고 빅오가 O(n^2)인 DP 문제를 하나 던져주고 간다.

---

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

( 비슷해서 그런가 문제 번호가 하나 차이네 )

사고과정

증가수열이 중첩되어 있다면?? 앞부분에서 가장 길다고 생각된 수열이 뒤에서 반전된다면?
Ex) [ 10, 20, 80, 10, 30, 50, 70 ]

결국 바로 앞부분만 보고는, 단편적으로만 보고는 결정할 수 없다. i번째 요소에서 가장 긴 부분 수열을 결정하기 위해서는 앞에 모든 요소들 중에서 가장 긴 부분 수열을 채택할 수 있어야 한다.

그렇기 때문에 i번째 요소를 조회하는 for 문과 i번째 이전 요소 j번째 요소를 조회하는 for문 두개가 필요해 이중 for문을 사용하여야만 한다. 이에 대한 자세한 논리는 생략...

import sys

N = int(sys.stdin.readline().rstrip("\n"))

line = list(map(int,sys.stdin.readline().rstrip("\n").split()))
dp = [0 for _ in range(N)]

for i in range(N) :
    for j in range(i) :
        if (line[j] < line[i]) and (dp[i]<dp[j]):
            #뒤의 조건이 없으면 무시돼버리는 경우가 생길 수 있음
            dp[i]=dp[j]
    dp[i]+=1
            
print(max(dp))