11055번 - 가장 큰 증가하는 부분수열

가장 큰 증가하는 부분수열을 구하는 문제입니다.
이전에 풀었던 가장 긴 증가하는 부분수열을 응용한 문제라고 보시면 될 것 같습니다.

import copy

n = int(input())
lst = list(map(int,input().split()))
dp = copy.deepcopy(lst)

먼저 dp를 list와 똑같이 초기화해줍니다. 왜냐하면 현재 문제에서 제일 작게 나올 수 있는 값은 부분 수열의 합산이므로 결과적으로 자기 자신입니다.

for i in range(len(lst)):
    for j in range(i):
        if lst[i] > lst[j]:
            dp[i] = max(dp[i],lst[i]+dp[j])

그리고 현재 조사중인 인덱스가 이전 인덱스보다 더 크다면 현재 dp값과 그 이전 인덱스의 dp값 + 현재 인덱스의 합산을 대조하여 더 큰값을 현재 인덱스의 dp값에 대입해줍니다.

해당 문제 테케대로라면 이런씩으로 나옵니다.

print(max(dp))

마지막으로 dp 출력해주면 됩니다.

---

---

1965번 - 상자넣기

가장 긴 증가하는 부분수열을 문제화한 문제입니다.

n = int(input())
lst = list(map(int,input().split()))
dp = [1]*len(lst)

1이 수열의 최솟값이므로 받아주고(여기선 박스)

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

현재값이 이전 값보다 크다면 현재값의 dp와 이전값의 dp + 1값을 비교해 더 큰 값을 현재값의 dp로 넣어 가장 긴 증가하는 부분수열을 구체화해줍시다.

print(max(dp))

max(dp)출력하면 됩니다.

---

---

15988번 - 1,2,3 더하기 3

시간초과를 피하기 정말정말 어려운 문제입니다.

---

분석

일단 추가 시간 없음을 보자마자 단순 재귀나 백트래킹으로는 절대 시간 안에 못맞춘다고 봐야합니다.
그리고 조건중에 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. 라는 말이 있으면 DP라고 보는게 타당하겠죠...

위와 같은 과정으로 dp[n] = dp[n-1]+dp[n-2]+dp[n-3]이라는 점화식 도출이 가능합니다.

---

첫 번째 시도

T = int(input())
ans = []
for _ in range(T):
    ans.append(int(input()))

테스트케이스를 받아 ans에 추가해주겠습니다.

memo = [0]*(max(ans)+1)
memo[0] = 1
memo[1] = 2
memo[2] = 4

memo[2]까지는 점화식에서 음수취급 될 수도 있으므로 2까지 초기화를 진행해줍시다. 시간을 아끼기 위해 테스트케이스 중 제일 큰 값만 돌리고 나머지는 메모 참고하여 답을 출력하려 했습니다.

recursion(max(ans))

이제 재귀를 돌려줍니다.

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

시간 절약을 위해 sysinput과 재귀 depth 상한을 해제해주고

def recursion(n):
    if memo[n]:
        return memo[n]
    memo[n] = ( recursion(n-1) + recursion(n-2) + recursion(n-3) )%1000000009
    return memo[n]

메모이제이션에 있으면 memo[n]을 return, 아니라면 점화식에서 저 식을 나눈 값을 return 해줍시다.
1000000009를 지금 나눠주는 이유는 메모리 제한으로 인해 솔브가 안되는 상황을 방지하기 위해서입니다.
(분배법칙 / 모듈러 성질에 의거해 저기서 나누든 답 직전에 나누든 값 출력에 차이는 없습니다.)

for values in ans:
    print(memo[values-1])

출력시켜주면

답은 제대로 나오는데

역시나...

---

두 번째 시도

재귀는 가독성이 좋지만 callstack을 불러오므로 for문에 비해 상대적으로 시간복잡도가 높습니다.
따라서 for문으로 다시 구현해보기로 했습니다.

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

sysinput및 setrecursionlimit 선언해주고

T = int(input())
ans = []
for _ in range(T):
    ans.append(int(input()))

테스트케이스를 받아 ans에 추가합니다.

memo = [0]*(max(ans)+1)
memo[0] = 1
memo[1] = 2
memo[2] = 4

DP 초기화를 진행해주고

for i in range(3,len(memo)):
    memo[i] = ( memo[i-1] + memo[i-2] + memo[i-3] )% 1000000009

초기화 다음 단계인 3부터 끝까지 DP를 돌려줍시다.

for values in ans:
    print(memo[values-1])

그리고 ans에서 가장 큰 값을 DP돌려 MEMO에 기록했으니 memo값을 참조하여 답을 출력하면 됩니다.

---

---