[BOJ] 백준 9465번 - 스티커 (Python)

문제

문제 바로가기

해결

우선 다이나믹 프로그래밍 문제는, 해당 문제가 다이나믹 프로그래밍 문제임을 알아차리는 것부터가 시작이라고 생각한다.

우선 최근 내가 알고리즘 문제에서 다이나믹 프로그래밍이라고 생각하는 기준은 하나의 정형화된 코드로 해당 문제를 해결하기 어려울 것 같다고 느끼며, 제약이 많고, N이 증가할 수록 제약이 변칙적이고 필요한 연산 및 메모리의 양이 비례해 증가하는 경우 다이나믹 프로그래밍 문제라고 생각하고 먼저 접근한다.

다이나믹 프로그래밍이라고 생각을 했으면, 근본적으로 N이 증가함에 따라 DP 테이블에 d[n]의 값이 어떻게 들어가게 될지, 즉 점화식을 생각을 해야 한다.

우선 문제를 정확하게 파악을 해야 점화식을 제대로 작성할 수 있다.

해당 문제에서는 스티커의 1행에서 어떤 스티커를 뗐다면, 당연히 그 다음 스티커를 뗄 행은 2행이 된다는 것을 알 수 있다.

이러한 방식으로 접근을 하게 된다면, 각각의 i열의 1행의 최댓값은 앞의 i-2, i-1열의 2행 중 더 높은 값에 i열의 1행 값을 더한 값이 될 것이고, i열의 2행의 최댓값은 마찬가지로 앞의 i-2, i-1열의 1행 중 더 높은 값에 i열의 2행 값을 더한 값이 될 것이다.

이렇게 계속해서 2행에 대해 i열을 증가시켜나가며 n열까지 나아가다보면, n열에서는 두 행 중 큰 값을 반환하면 되는 것이다.

이를 식으로 나타내면 다음과 같다.

d[1][i] = max(d[2][i - 1], d[2][i - 2]) + s[1][i]
d[2][i] = max(d[1][i - 1], d[1][i - 2]) + s[2][i]

정답 제출

t = int(input())
result = []

for _ in range(t):
  n = int(input())
  s = [0] * 3
  d = [[0] * 100001 for _ in range(3)]

  for i in range(2):
    s[i + 1] = ([0] + list(map(int, input().split())))

  for i in range(1, n + 1):
    if i == 1:
      d[1][i] = s[1][i]
      d[2][i] = s[2][i]
    elif i == 2:
      d[1][i] = d[2][i - 1] + s[1][i]
      d[2][i] = d[1][i - 1] + s[2][i]
    else:
      d[1][i] = max(d[2][i - 1], d[2][i - 2]) + s[1][i]
      d[2][i] = max(d[1][i - 1], d[1][i - 2]) + s[2][i]

  result.append(max(d[1][n], d[2][n]))

for r in result:
  print(r)