백준 9465번: 스티커

문제링크:9465번: 스티커 (acmicpc.net)

9465번: 스티커

 

이 문제는 스티커가 2행 n열로 배치되어 있고, 스티커가 각각 점수를 가진다 했을때, 스티커를 하나 떼기로 정하면 상하좌우 4방면의 스티커는 뗄 수 없어지는 조건에서 뗀 스티커의 총 최대 점수 합을 구하는문제이다. 보통 행렬이 있고 상하좌우 등의 조건이 있으면 bfs를 사용했지만 n이 100000으로 매우 크고 행이 2행밖에 되지 않아 다른 방법을 생각해야 했다.

 

import sys

T=int(sys.stdin.readline().rstrip())

for _ in range(T):
    n=int(sys.stdin.readline().rstrip())
    lst=[]
    for _ in range(2):
        lst.append(list(map(int,sys.stdin.readline().rstrip().split())))
    maxscore=[[0,0,0] for _ in range(n)] #[위고르기, 아래고르기, 안고르기]
    maxscore[0][0]=lst[0][0]
    maxscore[0][1]=lst[1][0]
    for i in range(1,n):
        maxscore[i][2]=max(maxscore[i-1])
        maxscore[i][0]=max(maxscore[i-1][1]+lst[0][i],maxscore[i-1][2]+lst[0][i])
        maxscore[i][1]=max(maxscore[i-1][0]+lst[1][i],maxscore[i-1][2]+lst[1][i])
    print(max(maxscore[-1]))

DP를 사용해서 풀었다. 0열부터 끝열까지 각 열의 스티커를 고른다고 칠때 열마다 경우의 수는 0열 스티커 고르기, 1열 스티커 고르기, 그리고 스티커 안고르기 이렇게 3개의 경우가 있다. 점수를 저장할 maxscore 리스트를 만들었다. maxscore의 n열의 0행은 0열스티커를 고른 경우의 최대 점수, 1행은 1열 스티커를 고른 최대 점수, 2행은 스티커를 안고른 경우의 최대 점수로 해서 DP를 통해 끝까지 채워주어 maxscore의 마지막 열의 최대값을 출력하여 최대 점수를 출력할 수 있었다. DP문제를 많이 접해보지 않아서 maxscore의 리스트 형태를 어떻게 만들지 그리고 점화식을 어떤 형태로 만들지 고민하는데 꽤 많은 시간이 걸렸었다.