[백준/DP/ 9465] 스티커

이미지 클릭시, 문제로 이동됩니닷 :)

Sol

 

스티커를 떼게되면 위, 아래, 왼쪽, 오른쪽에 있는 스티커는 사용 할 수 없다.
예제 입력에 나와있는 260은 50,50,100,60의 합이다.

 

50 = (0,0)
50 = (1,1)
100 = (0,2)
60 = (1,4)

 

사용된 값은 모두 대각선에 있는 값이다.

0행인 경우에는 왼쪽 대각선 아래의 합
1행인 경우에는 위쪽 대각선의 합

 

위 값들을 구한 후 현재 내 값과 비교하여 max 값을 구해주면 된다.

 

import sys

# 테스트 케이스 수
T = int(sys.stdin.readline())
for _ in range(T):
  dp = []
  # 입력 받을 열 개수
  n = int(sys.stdin.readline()) 
  # 2열에 공백 기준으로 하나씩 담는다.
  for _ in range(2):
    dp.append(list(map(int, sys.stdin.readline().split())))

  # 기준 값
  if n > 1:
    dp[0][1] += dp[1][0]
    dp[1][1] += dp[0][0]

  # 대각선 합과 현재 내 값과 비교
  for j in range(2,n):
    dp[0][j] += max(dp[1][j-1], dp[1][j-2])
    dp[1][j] += max(dp[0][j-1],dp[0][j-2])

  # 최대값 출력, 끝쪽에 가장 큰 합이 있다. 끝 값끼리 비교
  # [[50, 40, 200, 140, 250], [30, 100, 120, 210, 260]]
  # 250과 260 비교
  print(max(dp[0][n-1], dp[1][n-1]))

런타임 에러가 미친듯이 나와 푸는데 애를 먹었다.

상냥이한테 새 스티커를 사주고싶다....

 

런타임 에러 소스와 정답 소스의 차이는 if n > 1: 유무이다.

조건을 꼼꼼하게 보는 습관을 들이자.