11.20 알고리즘 문제풀이

코테 연습

 

다이나믹 프로그래밍

첫 번째

https://www.acmicpc.net/problem/15486

15486번: 퇴사 2

import sys
input = lambda: sys.stdin.readline().rstrip()

N = int(input())
schedule = [[0]] + [list(map(int, input().split())) for _ in range(N)]

dp = [0] * (N+1)
max_value = 0

for idx in range(N, 0, -1):
    t, p = schedule[idx]
    if idx + t > N:
        if idx+t-1 == N:
            dp[idx] = max(max_value, p)
            max_value = dp[idx]
        else:
            dp[idx] = max_value
    else:
        dp[idx] = max(max_value, p + dp[idx+t])
        max_value = dp[idx]
print(dp[1])

import sys
input = lambda: sys.stdin.readline().rstrip()

N = int(input())
schedule = [list(map(int, input().split())) for _ in range(N)]

dp = [0] * (N+1)
max_value = 0

for idx in range(N-1, -1, -1):
    t, p = schedule[idx]
    if idx + t > N:
        dp[idx] = max_value
    else:
        dp[idx] = max(max_value, p + dp[idx+t])
        max_value = dp[idx]
print(dp[0])

어려운 문제였다.

dp 테이블을 정할 때는 인덱스로 어떤 값을 사용하고 value로 무엇을 넣을지 생각해야한다.

동전의 개수가 정해진 문제에서는 특정 index에서 동전의 크기대로 빼면서 접근하면

bottom-up으로 해결할 수 있었지만

위 문제는 어떤 상담이 특정 index에 끝나는지 알 수 없기 때문에

뒤로 접근해서 문제를 해결해야한다는 발상이 필요했다.

dp의 index로 오늘부터 퇴사 전날까지를

value로 현재 index부터 퇴사 전날까지의 최대 보상이라고 정해놓았다.

위와 아래 코드의 차이는 분기를 줄여서 약간의 최적화를 했다.

 

두 번째

https://www.acmicpc.net/problem/11053

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

import sys
input = lambda: sys.stdin.readline().rstrip()

N = int(input())
A = list(map(int, input().split()))

dp = [1] * N
for i in range(1, N):
    for j in range(i):
        if A[i] > A[j]:
            dp[i] = max(dp[i], dp[j]+1)
print(max(dp))

dp 연습으로 푸는 문제인데

꽤나 재밌는 주제의 문제를 만났다.

가장 긴 증가하는 수열은 크게 dp와 이진탐색으로 풀 수 있는데

둘 다 익혀둘 필요가 있다고 생각한다.

내일 이 주제를 정리해볼까 한다.

 

세 번째

https://www.acmicpc.net/problem/1912

1912번: 연속합

import sys
input = lambda: sys.stdin.readline().rstrip()

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

dp = [0] * n
dp[0] = numbers[0]
for idx in range(1, n):
    if numbers[idx] < 0 and dp[idx-1] + numbers[idx] < 0:
        dp[idx] = 0
        continue
    dp[idx] = dp[idx-1] + numbers[idx]
print(max(dp))

첫 코드는 위와 같다.

테스트 입력에서 모든 원소가 음수일 경우, 0을 반환함으로 실패했다.

위 코드를 작성한 아이디어는

음수를 만나는 순간 앞과 이어지는 경우는

"음수와 앞의 합이 0보다 클 경우밖에 없다." 이다.

모든 원소가 음수인 경우만 작동하지 않는 것 같아서 아래처럼 수정했다.

import sys
input = lambda: sys.stdin.readline().rstrip()

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

dp = [0] * n
dp[0] = numbers[0]
for idx in range(1, n):
    if numbers[idx] < 0 and dp[idx-1] + numbers[idx] < 0:
        dp[idx] = 0
        continue
    dp[idx] = dp[idx-1] + numbers[idx]

for idx in range(n):
    if numbers[idx] > 0:
        break
    if idx == n-1:
        if numbers[idx] < 0:
            value = max(numbers)
            dp = [value, value-1]
print(max(dp))

세상에 공개하면 안되는, 지저분한 코드가 나왔다.

나중에 다시 풀어봐야겠다.