문제
https://www.acmicpc.net/problem/9465
풀이
- 스티커 2n개
- 2행 n열로 배치
- 뗀 스티커의 왼쪽, 오른쪽, 위, 아래 사용 불가
- 스티커 점수합의 최대
DP를 활용한 문제
각 스티커에 점수를 부여하고 규칙에 따라 점수 최대값을 구하면 됩니다.
위 사진과 같이 스티커를 선택했을 경우 왼쪽, 오른쪽, 아래 스티커는 선택할 수 없습니다.
문제 해결을 위해 예시를 가지고 문제를 풀어봅시다.
다음과 같이 스티커 10개가 주어졌습니다.
이 스티커를 규칙(왼쪽, 오른쪽, 위, 아래 x)을 적용시켜 최대값을 구하면
50 + 50 + 100 + 60 = 260이 됩니다.
저는 dp 배열을 2행 n열로 선언했습니다.
dp = [[0] * n for _ in range(2)]초기값 dp[0][0], dp[1][0]은 arr[0][0], arr[1][0]과 같으므로 그대로 선언해줍니다.
다음으로 dp[0][1], dp[1][1] 값을 구해보겠습니다.
이 값을 구하기 위해서는 앞서 말한 규칙들을 잘 살펴봐야 합니다.
뗀 스티커의 왼쪽, 오른쪽, 위, 아래 스티커는 구할 수 없다고 했으므로
arr[1][0] 값만 더할 수 있습니다.
마찬가지로 dp[1][1]도 arr[0][0]만 더할 수 있습니다.
dp[0][1] = dp[1][0] + arr[0][1] # 직전값 + 현재 위치
dp[1][1] = dp[0][0] + arr[1][1]다음으로 dp[0][2], dp[1][2] 값을 구해볼게요.
dp[0][2]는 dp[1][1] 값을 선택할 수 있습니다.
그러나 dp[1][0]이 클 경우도 고려해야 합니다.
제가 만든 예제를 보며 설명해보겠습니다.
위와 같이 주어졌을 때, (0,2) 값을 구하려면 직전 값은 구하지 못하므로 (1,1)값을 선택할 수 밖에 없다고 생각할 수 있습니다.
그러나 (1,0) 값이 더 크기 때문에 (1,0)을 선택할 수도 있습니다.
이렇게 우리는 dp[0][2]를 구할 때, dp[1][1], dp[1][0]을 비교해야 합니다.
이를 토대로 점화식을 작성하면
dp[0][i] = max(dp[1][i-1], dp[1][i-2]) + arr[0][i]
dp[1][i] = max(dp[0][i-1], dp[0][i-2]) + arr[1][i]이제 이를 가지고 코드를 작성하면 됩니다.
코드
import sys
input = sys.stdin.readline
for _ in range(int(input())):
n = int(input())
arr = [list(map(int,input().split())) for _ in range(2)]
# n이 1일 경우 dp 배열을 생성하고 선언하는 연산은 필요 없기 때문에
# 입력값 중 최대값 바로 출력
if n == 1:
print(max(arr[0][0], arr[1][0]))
continue # 다음 테스트 케이스
dp = [[0] * n for _ in range(2)]
dp[0][0] = arr[0][0]
dp[1][0] = arr[1][0]
dp[0][1] = dp[1][0] + arr[0][1]
dp[1][1] = dp[0][0] + arr[1][1]
# n이 2일 경우
if n == 2:
print(max(dp[0][1], dp[1][1]))
continue
# n이 2 이상일 경우
for i in range(2,n):
dp[0][i] = max(dp[1][i-1], dp[1][i-2]) + arr[0][i]
dp[1][i] = max(dp[0][i-1], dp[0][i-2]) + arr[1][i]
print(max(dp[0][-1], dp[1][-1]))