boj.kr/9465 스티커 (silver1) 파이썬 풀이

1. dp 배열을 스티커 리스트로 초기화

2. 1부터 스티커 리스트 길이만큼 순회하면서 아래를 반복

2.1. 1번째이면 대각선 방향의 0번째 스티커 값을 더하기

2.2. dp[0][i], dp[1][i]으로 각각 대각선 방향의 i-1, i-2번째 값 중 더 큰값을 더하기

3. dp에서 최대값을 출력

 

T = int(input())
for _ in range(T):
    N = int(input())
    dp = [list(map(int, input().split())) for _ in range(2)]
    for i in range(1, N):
        if i == 1:
            dp[0][1] += dp[1][0]
            dp[1][1] += dp[0][0]
        else:
            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]))

 

dp[y][x] 값을 해당 좌표의 스티커가 선택되는 경우의 누적합의 최대값으로 저장할 수 있다.

 

참고출처

"[백준] 9465번(python 파이썬)", pacific-ocean.tistory.com, 2019년 9월 30일 수정, 2023년 6월 11일 접속, https://pacific-ocean.tistory.com/197