tc = int(input())
for _ in range(tc):
n = int(input()) # 한 라인의 스티커 개수
dp = [list(map(int, input().split())) for _ in range(2)] # 주어진 스티커 배열
if n > 1:
dp[0][1] += dp[1][0] # 점화식에 i-2가 있기때문에 처음 값은 직접 더해준다. (현재자리의 왼쪽 대각선자리)
dp[1][1] += dp[0][0]
for i in range(2, n):
# 선택할 수 있는 두 자리에 있는 점수 중, 큰 점수와 현재 스티커와 더해주기
dp[0][i] += max(dp[1][i-2], dp[1][i-1])
dp[1][i] += max(dp[0][i-2], dp[0][i-1])
print(max(dp[0][-1], dp[1][-1])) # 마지막 자리에서 여태까지 더한 제일 큰 점수 선택
점화식 설명
- i = 9라고 한다면, 9 자리에서는 7과 10의 자리를 택할 수 없다. 그렇기에 9의 자리에서 택할 수 있는 자리는 6과 8이 남는다. (5의 경우는 5를 택하면 8도 택할 수 있기 때문) 그렇기 때문에 점화식은
max(dp[0 or 1][i-2], dp[0 or 1][i-1])
이 된다.
그렇기 때문에 둘 중 더 큰 점수를 저장하고 있는 곳을 택하고, 해당 자리의 점수를 더하면 해당 자리에서 고를 수 있는 최대 점수가 된다. - 그리고 1의 자리 (
dp[0][0]
)에서 출발한 경우와 2의 자리(dp[1][0]
)에서 출발한 경우. 이렇게 두가지 수가 나오니 마지막에 둘 중에 더 큰 점수를 정답으로 가진다.
처음 풀이
tc = int(input())
for _ in range(tc):
n = int(input()) # 한 라인의 스티커 개수
sticker = [list(map(int, input().split())) for _ in range(2)] # 주어진 스티커 배열
dp = [[0 for _ in range(n)] for _ in range(2)] # dp 배열
dp[0][0] = sticker[0][0] # 초기 스티커 넣어주기
dp[1][0] = sticker[1][0]
if n == 1:
print(max(dp[0][0], dp[1][0]))
else:
dp[0][1] = sticker[1][0] + sticker[0][1]
dp[1][1] = sticker[0][0] + sticker[1][1]
for i in range(2, n):
# 선택할 수 있는 두 자리에 있는 점수 중, 큰 점수와 현재 스티커와 더해주기
dp[0][i] = max(dp[1][i-2], dp[1][i-1]) + sticker[0][i]
dp[1][i] = max(dp[0][i-2], dp[0][i-1]) + sticker[1][i]
print(max(dp[0][-1], dp[1][-1])) # 마지막 자리에서 여태까지 더한 제일 큰 점수 선택
dp 배열을 만들어서 거기에 해당자리에서 구할 수 있는 최대 점수를 넣어주는 코드로 짰는데, 풀고 보니 dp 배열을 굳이 새로 만들어 줄 필요가 없다고 생각하여 맨 위의 코드처럼 수정하게 되었다.
'Algorithm > Baekjoon' 카테고리의 다른 글
[Python] 9205. 맥주마시면서 걸어가기 (0) | 2021.10.19 |
---|---|
[Python] 2293. 동전 1 (0) | 2021.10.02 |
[Python] 11047. 동전 0 (0) | 2021.09.28 |
[Python] 1463. 1로 만들기 (0) | 2021.09.28 |
[Python] 11052. 카드 구매하기 (0) | 2021.09.26 |