[DP] 2문제+복습

1. 금광

코드

t = int(input())

for _ in range(t):
    n,m = map(int,input().split())
    dp=[]
    line= list(map(int,input().split()))
    
    index = 0
    #그래프로 바꿔주기
    for _ in range(n):
        dp.append(line[index:index+m])
        index+=m
    
    #i,j번째를 기준으로 생각
    for j in range(1,m):
        for i in range(n):
            #왼쪽 위
            if i==0:
                left_up = 0
            else:
                left_up = dp[i-1][j-1]
            #왼쪽 아래
            if i==n-1:
                left_down = 0
            else:
                left_down = dp[i+1][j-1]
            
            #왼쪽 -> 항상 가능
            left = dp[i][j-1]
            
            dp[i][j] +=max(left,left_down,left_up)
    
    result =0
    for i in range(n):
        result =max(result,max(dp[i]))
    print(result)

처음에 인덱스를 엄청 헷갈려 했었다 ㄱ-
(i,j)의 위치에서 가장 큰 값을 찾는 방식으로 했다.
(i,j)를 기준으로 보면 왼쪽 위, 왼쪽, 왼쪽 아래에서 i,j로 오는 것이기 때문에 각각을 구해서 최댓값을 구했다.

2. 퇴사

링크 - https://www.acmicpc.net/problem/14501
나는 일단 입사부터 하고 싶다ㅎ

코드

import sys
input = sys.stdin.readline

n = int(input())
t=[]
p=[]
max_val = 0

#입력받기
for i in range(n):
    a,b = map(int,input().split())
    t.append(a)
    p.append(b)


dp=[0]*(n+1)

#거꾸로
for i in range(n-1,-1,-1):
    time = i+t[i] #i번째를 선택했을 때 날짜
    #기간 내에 끝나는 일이라면
    if time<=n:
        dp[i]=max(max_val,p[i]+dp[time])
        max_val =dp[i]
    else:
        dp[i] = max_val

print(max_val)

처음에는 1일차부터 시작을 하는 걸로 생각했다.
그런데 ti의 값으로 최대 5까지 들어올 수 있기 때문에 그것을 고려해줘야 하는데 그게 내 머리로는 까다로웠다.

답지를..참고해서.. 반대로 가는 경우라는 것을 알게 되었고 기간 내에 끝낼 수 있다면 점화식을 대입하는 방식으로 구현했다.

3. 개미전사

코드

n = int(input())

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

dp=[0]*n
dp[0] = arr[0]
dp[1]=arr[1]
for i in range(2,n):
    dp[i] = max(dp[i-2]+arr[i],dp[i-1])

print(dp[-1])

복습문제고 짝수일 때와 홀수일 때를 구분하는 문제였다.
모든 시험이 이러면 얼마나 좋을까 ㄱ-

다른 알고리즘도 개못하지만 dp는 진심 개개개개개못하는거 같다 후....