[백준 9465번] 파이썬 - 스티커

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

9465번: 스티커

 

# 조건

• 상근이의 여동생 상냥이는 문방구에서 스티커 2n개를 구매
• 스티커는 아래 그림과 같이 2행 n열로 배치
• 스티커 한 장을 떼면, 그 스티커와 변을 공유하는 스티커는 모두 찢어져 사용 불가
• 점수의 합이 최대가 되도록 스티커를 붙여라

 

 

# 입력

• 첫째 줄에 테스트 케이스의 개수 T가 주어진다.
• 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다.
• 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 점수이다.
• 연속하는 두 정수 사이에는 빈 칸이 하나 있다. 점수는 0보다 크거나 같고, 100보다 작거나 같은 정수이다.

 

# 접근 방법

• dp를 이용하여 풀어주면 된다.
• 0번 줄의 경우 -> 선택한다면 다음 줄은 1번줄만 가능
• 1번 줄의 경우 -> 선택한다면 다음줄은 0번만 가능
• 하지만 dp를 이용하여 최댓값을 선택해줄 때
  • 2열 전의 값도 비교해주어야 한다.
  • 다음 열의 값이 10, 10이고
  • 그 다음 열의 값이 100인 경우 무조건 그 다음꺼 선택하는 것이 좋다.
• 따라서, 지그재그로 선택하는 과정에서 한 칸을 건너 뛰는 경우를 생각해주어야 한다.
• 99퍼센트에서 -> 인덱스에러
  • N이 1인 경우가 있으므로 예외처리해준다.

 

import sys  
sys.stdin = open('input.txt')  
  
T = int(input())  
for tc in range(T):  
    N = int(input())  
    stick = [[*map(int, input().split())] for _ in range(2)]  
    if N == 1:  
        print(max(stick[0][0], stick[1][0]))  
    else:  
        dp = [[0] * N for _ in range(2)]  
        dp[0][0] = stick[0][0]  
        dp[1][0] = stick[1][0]  
        dp[0][1] = stick[0][1] + dp[1][0]  
        dp[1][1] = dp[0][0] + stick[1][1]  
  
        for j in range(2, N):  
            for i in range(2):  
                dp[i][j] = max(dp[i-1][j-1], dp[i-1][j-2]) + stick[i][j]  
  
        print(max(dp[0][-1], dp[1][-1]))