코딩테스트

백준 DP - 스티커(파이썬)

수연 (Suyeon) 2023. 11. 27. 23:41
반응형

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

 

9465번: 스티커

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의

www.acmicpc.net

 

 

스티커에는 2행 n열 배열로 이루어져 있는데 저는 1행에서의 큰 값과 2행에서의 큰 값을 비교하면서 두 변을 공유하는 데이터에는 -1로 변경해 주면서 사용할 수 있는 스티커들만 골랐습니다. 정답은 맞혔지만 문제에서는 시간초과로 실패하고 말았습니다..

T = int(input())

def match(dp, row, idx):
  if(idx > 0 and idx < n-1):
    dp[row][idx-1] = -1
    dp[row][idx+1] = -1
    dp[row][idx] = -1
  elif idx == 0:
    dp[row][idx+1] = -1
    dp[row][idx] = -1
  else:
    dp[row][idx-1] = -1
    dp[row][idx] = -1
  if (row == 0):
    dp[row+1][idx] = -1
  else:
    dp[row-1][idx] = -1

for i in range(T):
  n = int(input())
  dp = []
  sum = 0
  for i in range(2):
    dp.append(list(map(int, input().split())))

  while True:
    max1 = max(dp[0])
    max2 = max(dp[1])
    if (max1 == -1) and (max2 == -1):
      break
    elif max1 >= max2:
      sum += max1
      idx = dp[0].index(max1)
      match(dp, 0, idx)
    elif max1 < max2:
      sum += max2
      idx = dp[1].index(max2)
      match(dp, 1, idx)

  print(sum)

 

그래서 다른 분들의 코드를 살펴보았더니 현재 위치에 있는 스티커와 대각선을 이루고 있는 스티커와 전 전 대각선을 이루고 있는 스티커 이 두 개 중 큰 값과 합해서 문제를 해결하는 방법을 얻게 되었습니다.

참고했던 코드는 https://jyeonnyang2.tistory.com/42 이 포스팅입니다.

T = int(input())

for _ in range(T):
  n = int(input())
  dp = []
  for _ in range(2):
    dp.append(list(map(int, input().split())))
  dp[0][1] += dp[1][0]
  dp[1][1] += dp[0][0]
  for i in range(2, n):
    dp[0][i] += max(dp[1][i-1], dp[1][i-2])
    dp[1][i] += max(dp[0][i-1], dp[0][i-2])
  print(max(dp[0][-1], dp[1][-1]))

 

DP 문제는 이전 값과 비교하면서 푸는 문제인데 저는 뒤에 가져다 붙여서 푸는 문제는 이제 풀 수 있지만 아직 이런 문제는 어려운 것 같습니다. 더욱 많이 공부하고 노력해야겠어요!!

 

 

 

728x90