[알고리즘/동적 계획법] 9465번 : 스티커 - python

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

9465번: 스티커

 

---

• 문제
• 소요시간: 실패

 

---

• 설계하기(접근방법) 

1. 테스트 케이스와 리스트를 입력받는다

 

2. 알고리즘 해석

일반적으로 계속 대각선을 더해 나간다

리스트를 dp1, dp2 로 선언한다

 

1) 고려해야 할 사항 中 복잡한 것은 다음 대각선의 수를 포기하고, 다다음 대각선의 수를 더하는 경우, 선택을 하지 않고 넘어가는 경우의 수가 있다.

200 20 40  

120 10 60

-> 200 + 10 + 40 or 200 + X + 60

2) 먼저 1번째 인덱스와 대각선의 0번째 인덱스를 더한다.50 + 50, 30 + 10

 

3) 다음 인덱스부터는 이전의 dp를 더할지, 아니면 이전전의 dp를 더할지 값을 비교하여 그중 큰 값을 더한다.

max(dp[j] += max(dp[j-1], dp[j-2])

 

3. 두 리스트 중 max값을 출력한다.

 

 

---

• 코드(출력)

import sys

input = sys.stdin.readline

t = int(input())

for i in range(t):
    n = int(input())
    dp1 = list(map(int, input().split()))
    dp2 = list(map(int, input().split()))
    for j in range(1, n):
        if j == 1:
            dp1[j] += dp2[j-1]
            dp2[j] += dp1[j-1]
        else:
            dp1[j] += max(dp2[j-1], dp2[j-2])
            dp2[j] += max(dp1[j-1], dp1[j-2])
    print(max(dp1[n-1], dp2[n-1]))

---

• 얻어갈 부분

1. 점화식을 제대로 세우지 못했다. 풀이를 보고도 처음에는 잘 이해하지 못했다. dp를 기준으로 다음값을 비교하지 말고, 이전의 값을 비교하는 방식으로 접근하자