문제를 쓱 읽어 보면 DP의 냄새가 솔솔솔~ 난다.
딱 봐도 그리디로 풀 수 없고 완전 탐색을 진행해야만 풀 수 있는 상황이다. 그렇다면 역시 DP로 풀어야한다.
DP로 풀기 위해서는 다음 단계에 영향을 미쳐야 한다. 즉, 선택한 스티커의 상하좌우에 위치한 다른 스티커를 선택할 수 없다. 우선 dp를 이차원배열이라 한다. 또한 dp에는 각 행별로 열까지의 최댓값을 가진다.
따라서 천천히 생각해보자 만약 0열의 i를 뽑을 것이라면 0열의 dp[0][i-1]을 뽑을 수 없다. 따라서 0열이 아닌 1열의 i-1까지인 dp[1][i-1]을 더할 수 있다. 그러면 식은 dp[0][i] = dp[1][i-1] 이다.
또한 한가지를 더 생각해 보아야 한다. i-1의 열의 스티커의 값이 형편 없다면 이걸 무시하고 i-2열에서 가장 큰 값인 max( dp[0][i-2], dp[1][i-2] ) 값을 가져오면 된다.
그러면 점화식이 나온다.
dp[0][i] = score[0][i]+ max(dp[1][i-1], max(dp[0][i-2], dp[1][i-2]))
dp[1][i] = score[1][i]+ max(dp[0][i-1], max(dp[0][i-2], dp[1][i-2]))
하 쉽게 설명하고 싶은데 쉽게 설명이 안된다. 만약 이해했다면 당신은 천재.
그럼 이제 코드를 짜주면 끝이다.
t = int(input())
for _ in range(t):
n = int(input())
score = []
for i in range(2):
score.append(list(map(int, input().split())))
dp = [[0 for i in range(n)] for i in range(2)]
for i in range(n):
if i == 0:
dp[0][i] = score[0][i]
dp[1][i] = score[1][i]
elif i == 1:
dp[0][i] = score[0][i] + dp[1][i-1]
dp[1][i] = score[1][i] + dp[0][i-1]
else:
# 자신 포함 사이드 최대
# 자신 포함
dp[0][i] = score[0][i]+ max(dp[1][i-1], max(dp[0][i-2],dp[1][i-2]))
dp[1][i] = score[1][i]+ max(dp[0][i-1], max(dp[0][i-2],dp[1][i-2]))
print(max(dp[0][n-1],dp[1][n-1]))
결론 : DP풀때 이차원 배열 어색해서 잘 못 풀었는데 좋은 문제인거 같다.
'알고리즘' 카테고리의 다른 글
[python3] 백준 1520 풀이 ( 내리막길, DP, DFS, 그래프 ) (0) | 2021.08.11 |
---|---|
[python3] 백준 2293 풀이 ( 동전 1, 다이나믹 프로그래밍 ) (0) | 2021.08.10 |
[c++] 백준 1629 풀이 ( 곱셈, 분할 정복을 이용한 거듭제곱, long long ) (0) | 2021.08.09 |
[python3] 백준 2252 풀이 ( 줄세우기, 위상정렬, DAG, 그래프 ) (0) | 2021.08.07 |
[c++] 백준 11657 풀이 ( 타임머신, 최단경로, 벨만-포드, 음수 가중치 ) (0) | 2021.08.06 |