[Python]9465. 스티커

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

9465번: 스티커

---

 

고민하다가 강의를 듣고 푼 문제.

풀면서 배운 점

1. 굳이 DP의 index를 가지고 상태 표현을 다 할 필요가 없다.

 

기존 방법, i = 1 일때 )

• 위를 선택하지 않을 때        DP[i][0][0] = 0
• 위를 선택할 때                     DP[i][0][1] = 50
• 아래를 선택하지 않을 때    DP[i][1][0] = 0
• 아래를 선택할 때                 DP[i][1][1] = 30

해결 방법, i = 1 일때)

• 어느것도 선택하지 않을  때     DP[i][0] = 0
• 위만 선택할 때                            DP[i][1] = 50
• 아래만 선택할 때                        DP[i][2] = 30

 

2. 덧셈 연산 뿐만 아니라, min 또는 max 등의 함수도 활용하자.

 

너무 기본 연산으로만 모든 경우를 표현하려 했었다. ㅜㅜ

for _ in range(int(input())):
    MAX = 100000
    DP = [[0]*3 for _ in range(MAX+1)]
    n = int(input())
    sticker = [list(map(int, input().split())) for _ in range(2)]
 
    for i in range(1, n+1):
        DP[i][0] = max(DP[i - 1][0], DP[i - 1][1], DP[i - 1][2])
        DP[i][1] = max(DP[i - 1][0], DP[i - 1][2])+sticker[0][i-1]
        DP[i][2] = max(DP[i - 1][0], DP[i - 1][1])+sticker[1][i-1]
 
    print(max(DP[n]))