세상을 더 좋게

[백준] 9465 '스티커' 파이썬(python) 본문

Algorithm/DP

[백준] 9465 '스티커' 파이썬(python)

나는SOU 2021. 12. 23. 00:00

https://www.acmicpc.net/problem/9465

 

9465번: 스티커

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의

www.acmicpc.net

tc = int(input())
for _ in range(tc):
    n = int(input())
    dp = []
    for _ in range(2):
        dp.append(list(map(int, input().split())))
    dp[0][1] += dp[1][0]
    dp[1][1] += dp[0][0]
    
    for i in range(2, n):
        dp[0][i] += max(dp[1][i-1], dp[1][i-2])
        dp[1][i] += max(dp[0][i-1], dp[0][i-2])
        
    print(max(dp[0][n-1], dp[1][n-1]))

Point

  • dp테이블을 활용한 DP 문제

'Algorithm > DP' 카테고리의 다른 글

[백준] 2156 '포도주 시식' 파이썬(python)  (0) 2021.12.24
[백준] 1932 '정수 삼각형' 파이썬(python)  (0) 2021.12.24
[백준] 11057 '오르막 수' 파이썬(python)  (0) 2021.12.22
[백준] 1309 '동물원' 파이썬(python)  (0) 2021.12.21
[백준] 1149 'RGB거리' 파이썬(python)  (0) 2021.12.21
'Algorithm/DP' Related Articles more