[알고리즘 기초 1/2] DP 1

15990번: 1, 2, 3 더하기 5

아이디어 자체는 떠올라서 구현까지 완료했으나 시간초과.. 왜죠?
mod 연산을 효율적으로 구현하는 방법이 떠오르질 않는다..

# 시간초과 코드
import sys
input = sys.stdin.readline

n = int(input())
arr = []
for _ in range(n) : arr.append(int(input()))

endnum = max(arr)

dp = [[0, 0, 0], [1, 0, 0], [0, 1, 0], [1, 1, 1]]


for i in range(4, endnum + 1) :
    tmp_dp = []
    for j in range(3) :
        tmp_dp.append((sum(dp[i - (j + 1)]) - dp[i - (j + 1)][j]))

    dp.append(tmp_dp)

for i in arr :
    print(sum(dp[i]) % 1000000009)

참고 여부 : O (mod 연산 부분만..)

나의 똥고집으로 dp 초기화 부분만 바꿔서 해보았다.
결과는 시간 초과

tmp_dp를 통해서 넣어주는 부분을 바꿔보자.. for문을 사용하는 것이 속도를 느리게 하는가? 어셈블리어에서 배운 걸 떠올려보면 그럴 수 있다고 생각이 된다.

dp = [[0 for _ in range(3)] for _ in range(100001)]
dp[0] = [0, 0, 0]
dp[1] = [1, 0, 0]
dp[2] = [0, 1, 0]
dp[3] = [1, 1, 1]

한번 더 똥고집을 부려서 dp[i][0~2] 마다 모듈러 연산을 해주지 않고 마지막 프린트문에서만 모듈러를 해봤다.
결과는 시간초과! 이건 진짜 궁금하다. 왜지?

chatGPT가 말해준 바에 의하면

시간초과 코드에서는 결과값을 출력할 때마다 나머지를 취하지 않고 큰 정수 값들을 그대로 사용한다면, 연산 중에 정수 값이 너무 커져서 처리하는 데에 시간이 오래 걸릴 수 있습니다. 결과적으로 이로 인해 시간초과가 발생할 수 있습니다.
통과 코드에서는 각 계산마다 결과 값에 대한 나머지를 적용하여, 중간 계산에서의 오버플로우 문제를 예방하면서도 정확한 결과를 얻을 수 있기 때문에 시간초과가 발생하지 않는 것입니다.

라고 한다. 이해 완료..

# 통과 코드
for i in range(4, endnum + 1) :
    dp[i][0] = (dp[i - 1][1] + dp[i - 1][2]) % 1000000009
    dp[i][1] = (dp[i - 2][0] + dp[i - 2][2]) % 1000000009
    dp[i][2] = (dp[i - 3][0] + dp[i - 3][1]) % 1000000009

for i in arr :
    print(sum(dp[i]) % 1000000009)
    
# 시간초과 코드
for i in range(4, endnum + 1) :
    dp[i][0] = (dp[i - 1][1] + dp[i - 1][2]) 
    dp[i][1] = (dp[i - 2][0] + dp[i - 2][2]) 
    dp[i][2] = (dp[i - 3][0] + dp[i - 3][1]) 

for i in arr :
    print(sum(dp[i]) % 1000000009)

14002번: 가장 긴 증가하는 부분 수열 4

내 옛날 코드인.. 증가하는 부분 수열 1을 참고했다.
dp를 배열로 저장해서 배열의 마지막 요소가 현 요소보다 작으면 append 해주기

n = int(input())
arr = list(map(int, input().split()))

dp = [[arr[i]] for i in range(n)]

for i in range(1, n) :
    for j in range(i) :
        if arr[j] < arr[i] and len(dp[j]) + 1 > len(dp[i]) and dp[j][-1] < arr[i] :
            dp[i] = dp[j].copy()
            dp[i].append(arr[i])

dp.sort(key=len)
dp[-1].sort()
print(len(dp[-1]))
print(*dp[-1])

1309번: 동물원

일단 DP 챕터에 있다는 점에서 힌트를 얻었다. DP라는걸 몰랐으면 못 풀었을 것 같은데... 윗줄의 결과에 따라서 아랫줄이 영향 받는다는 점에서 DP임을 알아채야할 것 같다.

n = int(input())

dp = [[0 for _ in range(3)] for _ in range(n + 1)]

dp[1] = [1, 1, 1]

for i in range(2, n + 1) :
    dp[i][0] = (dp[i - 1][0] % 9901 + dp[i - 1][1] % 9901 + dp[i - 1][2] % 9901)
    dp[i][1] = (dp[i - 1][0] % 9901 + dp[i - 1][2] % 9901)
    dp[i][2] = (dp[i - 1][0] % 9901 + dp[i - 1][1] % 9901)

print(sum(dp[-1]) % 9901)

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

부분 수열 문제는 조건만 바꿔주면 통과 된다.
dp 배열을 갱신하는 조건을 추가해주었다.

n = int(input())
arr = list(map(int, input().split()))

dp = [[arr[i]] for i in range(n)]

for i in range(1, n) :
    for j in range(i) :
        if arr[j] < arr[i] and len(dp[j]) + 1 > len(dp[i]) and dp[j][-1] < arr[i] :
            if (sum(dp[j]) + arr[i]) > sum(dp[i]) :
                dp[i] = dp[j].copy()
                dp[i].append(arr[i])

dp.sort(key=sum)
print(sum(dp[-1]))

11054번: 가장 긴 바이토닉 부분 수열

참고 여부: OOO!!!!

뒤집어 풀다니.. 당신은 천재신가.
현재 가리키는 인덱스가 현재부터 뒤까지의 부분 수열의 길이라는 점을 이용해서 reverse와 일반 배열을 더해서 최대값이 되는 부분을 찾아주었다. 둘이 Sk에서 겹치므로 -1을 해주어야함

n = int(input())
arr = list(map(int, input().split()))
reversed_arr = arr[::-1]

increaseDp = [1 for _ in range(n)]
decreaseDp = [1 for _ in range(n)]

for i in range(1, n) :
    for j in range(i) :
        if arr[j] < arr[i] :
            increaseDp[i] = max(increaseDp[i], increaseDp[j] + 1)
        if reversed_arr[j] < reversed_arr[i] :
            decreaseDp[i] = max(decreaseDp[i], decreaseDp[j] + 1)

result = [0 for i in range(n)]
for i in range(n):
    result[i] = increaseDp[i] + decreaseDp[n - i - 1] - 1

print(max(result))

13398번: 연속합 2

참고 여부 : O

문제

n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다. 또, 수열에서 수를 하나 제거할 수 있다. (제거하지 않아도 된다)
예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 수를 제거하지 않았을 때의 정답은 12+21인 33이 정답이 된다.
만약, -35를 제거한다면, 수열은 10, -4, 3, 1, 5, 6, 12, 21, -1이 되고, 여기서 정답은 10-4+3+1+5+6+12+21인 54가 된다.

처음엔 연속된 수열을 구하고 이를 최대로 하기 위해서 min값을 제거해주려 했다. 하지만 그런 식으로는 {10, -4, 3, 1, 5, 6, -100, 12, 21, -1}의 연속합을 구하지 못한다.

긴 바이토닉 수열을 풀었던 것처럼 뒤집어서 접근 했어야 했다.

import sys
input = sys.stdin.readline

n = int(input())
arr = list(map(int, input().split()))
reversed_arr = arr[::-1]

L2R_dp = [[] for _ in range(n)]
R2L_dp = [[] for _ in range(n)]

L2R_dp[0] = arr[0]
R2L_dp[0] = reversed_arr[0]
for i in range(1, n) :
    L2R_dp[i] = max(arr[i], L2R_dp[i - 1] + arr[i])
    R2L_dp[i] = max(reversed_arr[i], R2L_dp[i - 1] + reversed_arr[i])

R2L_dp = R2L_dp[::-1]

unjump = max(L2R_dp)
maxValue = L2R_dp[0]
for i in range(1, n - 1) :
    maxValue = max(maxValue, R2L_dp[i + 1] + L2R_dp[i - 1])

print(max(unjump, maxValue))

2133번: 타일 채우기

참고 여부: OOO!!!!
https://yabmoons.tistory.com/536
진짜 설명 잘해놓으심

진짜 너무 어렵다... 중복되는 타일들을 어떻게 처리해야 하는지가 관건이었다.

n = int(input())

dp = [0] * 31

dp[0] = 1
dp[2] = 3
dp[4] = 11

for i in range(6, 31, 2) :
    dp[i] += dp[i - 2] * dp[2]
    for j in range(0, i - 2, 2) :
        dp[i] += dp[j] * 2

print(dp[n])

17404번: RGB거리 2

rgb거리와 다른 점은 첫번째 집과 N번째, 즉 마지막 집의 색이 달라야한다는 것이다.

첫번째 집을 고정해서 값을 비교했다.
first_color + 1을 인덱스로 썼더니 인덱스 범위 초과가 떠서 -2로 변경. 어차피 3가지 색이니까 상관없다.
그리고 두번 틀렸는데.. 이건 answer의 값을 처음에 3000으로 잡았었다. 집이 1000개가 주어지고, 집을 칠하는 비용이 1000 이하니 1000 * 1000 + 1로 해주어야한다.

n = int(input())
tmp = []
for i in range(n) :
    tmp.append(list(map(int, input().split())))

import copy

ans = 1000 * 1000 + 1
for first_color in range(3) :
    dp = copy.deepcopy(tmp)
    dp[1][first_color - 2] += dp[0][first_color]
    dp[1][first_color - 1] += dp[0][first_color]
    if (n > 2) :
        dp[2][first_color] += min(dp[1][first_color - 1], dp[1][first_color - 2])
        dp[2][first_color - 2] += dp[1][first_color - 1]
        dp[2][first_color - 1] += dp[1][first_color - 2]

        for i in range(3, n) :
            dp[i][first_color] += min(dp[i - 1][first_color - 2], dp[i - 1][first_color - 1])
            dp[i][first_color - 2] += min(dp[i - 1][first_color], dp[i - 1][first_color - 1])
            dp[i][first_color - 1] += min(dp[i - 1][first_color], dp[i - 1][first_color - 2])

    ans = min([ans, dp[-1][first_color - 2], dp[-1][first_color - 1]])

print(ans)