[백준/python] 9465번 스티커

1. 문제

 

이 문제는 스티커를 뗄 때 얻을 수 있는 최대 점수를 구하는 문제이다.

그러나 스티커를 떼면 맞닿는 스티커들은 사용할 수 없어진다.

 

2. 풀이

이 문제는 코테 스터디에서 시간을 정해두고 풀었다.

20분 정도 소요되어서 풀었다.

이전에 풀어봤던 dp 문제들 덕에 금방 풀이 방법을 생각해냈다.

 

스티커 배열을 입력받고 그것과 같은 형태로 dp 테이블을 초기화한다.

자기 자신을 뜯을 경우에는 바로 왼쪽 칸은 뜯을 수 없고, 대각선에 있는 걸 뜯을 수 있다.

그래서 자신 + 왼쪽 대각선을 뜯은 값과 왼쪽 칸을 뜯은 값 중 최댓값으로 dp 테이블을 갱신한다.

마지막에는 모든 값 중 최댓값을 출력한다.

3. 코드

import sys
input = sys.stdin.readline

t = int(input()) #테스트케이스
for i in range(t):
    n = int(input()) #스티커 길이
    arr = [list(map(int, input().split())) for _ in range(2)] #스티커 배열
    dp = [[0]*n for _ in range(2)] #스티커 배열과 동일한 형태로 dp 초기화
    dp[0][0] = arr[0][0]
    dp[1][0] = arr[1][0]
    #자신 + 왼쪽 대각선 vs 바로 왼쪽 칸 중 더 큰 값으로 갱신
    for i in range(1, n):
        dp[0][i] = max(dp[1][i-1]+arr[0][i], dp[0][i-1])
        dp[1][i] = max(dp[0][i-1]+arr[1][i], dp[1][i-1])
    #최댓값 출력
    print(max(max(dp[0]), max(dp[1])))

4. 결과

 

시간을 정해두고 푸니 긴장감이 넘쳤고 그 덕에 더 빠르게 풀이방법을 찾을 수 있었다.

앞으로 문제를 풀 때도 시간을 정해두고 풀어야겠다.