2023/8/19

이코테 p375

import sys

input = sys.stdin.readline

T = int(input())  # 1000

for _ in range(T):  # 1000
  n, m = map(int, input().split())  # 20, 20
  graph = [[] for _ in range(n)]
  dp = [[0] * m for _ in range(n)]
  inputList = list(map(int, input().split()))

  for i in range(n):  # 400
    for _ in range(m):
      graph[i].append(inputList.pop(0))

  for i in range(n):
    dp[i][0] = graph[i][0]

  for j in range(1, m):
    for i in range(n):
      if i == 0:
        dp[i][j] = max(dp[i][j - 1], dp[i + 1][j - 1]) + graph[i][j]
      elif i == n - 1:
        dp[i][j] = max(dp[i - 1][j - 1], dp[i][j - 1]) + graph[i][j]
      else:
        dp[i][j] = max(dp[i - 1][j - 1], dp[i][j - 1],
                       dp[i + 1][j - 1]) + graph[i][j]

  result = []
  for i in range(n):
    result.append(dp[i][m - 1])

  print(max(result))

# 1 5 1 5
# 2 7 4 1
# 5 5 2 3
# 0 11 1 2

dp에 각 열마다 최대값을 집어 넣은 다음에

다음 열을 조회할때 전의 열의 최대값을 이용해 최대값을 찾는 알고리즘을 활용하였다.

이코테 p376

import sys

input = sys.stdin.readline

n = int(input())  # 1000

graph = []
dp = [[0] * n for _ in range(n)]

for _ in range(n):
  graph.append(list(map(int, input().split())))

dp[0][0] = graph[0][0]

for i in range(1, n):
  for j in range(i + 1):
    if j == 0:
      dp[i][j] = dp[i - 1][j] + graph[i][j]
    elif j == i:
      dp[i][j] = dp[i - 1][j - 1] + graph[i][j]
    else:
      dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j]) + graph[i][j]

print(max(dp[n - 1]))

전 문제랑 굉장히 비슷하다. 위에서 부터 계산을 하나하나 다하며 내려와 문제를 해결하였다.

p377

import sys

input = sys.stdin.readline

N = int(input())  # 1000
dp = [0] * 100
tCollect = [0]
pCollect = [0]

for _ in range(N):
  T, P = map(int, input().split())
  tCollect.append(T)
  pCollect.append(P)

#dp는 인덱스 0부터 시작하도록 합시다.

dp[0] = 0
for i in range(1, N + 1):
  nextIdx = i + tCollect[i]
  for j in range(nextIdx, 100):
    dp[j] = max(dp[i] + pCollect[i], dp[j])

for i in range(N + 2, 100):
  dp[i] = 0

print(max(dp))

…. dp 문제는 다 비슷한 것 같다 손쉽게 해결하였다.

2023/8/20

이코테 p380

import sys

input = sys.stdin.readline

N = int(input())  # 1000
dp = [0]*(N+1)

power = [0] + list(map(int, input().split()))
  
dp[N] = 1

for i in range(N-1 ,0,-1):    #2000번  
  myMax = 0
  
  for j in range(i+1,N+1):
    if power[i] > power[j] and dp[j] > myMax:
      myMax = dp[j]
      
  dp[i] = myMax + 1

print(N - max(dp))

전형적인 dp 문제이다. 단지 인덱스가 N에서 0으로 내려가면서 dp를 수행한게 차이점인데..

본질은 같다.