알고리즘 - Python / 백준 - 9465번 : 스티커

9465번: 스티커 (acmicpc.net)

9465번: 스티커

 

---

풀이

• 2행 n열의 스티커를 떼어 얻을 수 있는 가장 높은 점수를 출력하는 문제다.
• 그리디 알고리즘 문제라고 생각하고 풀어보았지만 , 풀던 도중 패턴이 있는 것 같아 DP로 풀어보았다.
• 좌측부터 스티커를 선택한다고 가정할시 , 그 다음 두칸뒤의 2줄의 스티커들이 선택할 수 있는 스티커들은 2칸전의 대각으로 이어진 스티커 2개 혹은 한칸 전의 대각선쪽의 1개를 선택하는 경우이다.
• 이 두가지 중 큰 경우를 선택해 점수를 계속해서 DP에 계속해서 업데이트 하고 마지막 DP배열의 값중 MAX 값을 출력한다.

 

import sys
n = int(sys.stdin.readline())
for _ in range(n):
    stack = []
    m = int(sys.stdin.readline())
    dp = [[0 for i in range(m)] for j in range(2)]
    for p in range(2):
        stack.append(list(map(int , sys.stdin.readline().split(" "))))
    if m != 1:
        dp[0][0] = stack[0][0]
        dp[1][0] = stack[1][0]
        dp[0][1] = stack[0][1] + stack[1][0]
        dp[1][1] = stack[1][1] + stack[0][0]
        for i in range(2,m):
            dp[0][i] = max(dp[1][i-1],dp[1][i-2]) + stack[0][i]
            dp[1][i] = max(dp[0][i - 1], dp[0][i - 2]) + stack[1][i]
        print(max(dp[0][m-1],dp[1][m-1]))
    else:
        print(max(stack[0][0],stack[1][0]))

---