[Python] 백준 9465: 스티커 (DP는 DFS보다 우선 고려되어야 한다.)

🔗 문제 링크

9465번: 스티커

💊 문제 요약

스티커가 2행 n열로 주어지며, 각 스티커에는 점수가 있다. 스티커를 한 장 떼었을 때 상하좌우의 스티커는 찢어져 못 쓰게된다. 이러한 조건에서 스티커의 떼었을 때 최대 점수를 알고 싶다.
테스트 케이스의 갯수 T가 주어지며, 각 테스트 케이스 별로 열의 갯수 n과 스티커의 점수가 2줄에 걸쳐 주어진다.

🌿 풀이 설명

처음에는 DFS를 통한 완전탐색으로 문제를 풀려고 했으나, 재귀함수 실행 시 int 매개변수 값이 자꾸 바뀌는 문제가 발생하여 코드가 오답을 뱉어냈다.

결국 정답 코드를 확인하고, DP 문제라는 것을 깨닫게 되었는데

기존에 DFS로 풀어야겠다고 결정하기 전에 DP를 고려하지 않았다는 것을 깨닫게 되었다.

 

이유는 직전에 풀었던 문제가 DFS 문제여서 이 문제도 같은 방식으로 풀 수 있겠다고 생각했었기 때문이다.

시간초과를 떠나서 이 문제를 DFS로 풀 수 있는 분은 댓글 부탁드립니다. 

 

 DP 문제에서 n번째 요소는 주로 다음 중 하나의 의미를 지닌다고 한다. (출처)

1. n번째까지 요소를 고려하였을 때의 최적값
2. n번째 요소를 선택하였을 때의 최적값

 

DP 문제는 특정 요소의 최적값을 탐색할 때, 해당 요소의 한 칸 뒤, 두 칸 뒤, 이런식으로 일정한 위치 관계에 있는 요소를 고려한다.

그런데 이 문제에서 DP matrix의 요소를 첫 번째와 같이 가정한다면, 최적을 단정하기 위해 일정한 위치 관계의 요소를 고려할 수 없다.

따라서  n번째 요소를 선택하였을 때의 최적값으로 가정하여 문제를 해결한다.

 

DP 시에, 어떤 위치의 요소에서 현재 요소를 더해야 최적값을 보장할 수 있을지 확인해야 한다.

DP 최적값 결정 시, 고려할 요소의 위치 탐색

 

맞닿은 스티커는 문제 조건 상 배제한다. (오른쪽 위)

현재 위치를 (i, j)라고 한다면 j-1번째 열 대각선 위치의 값에서 현재 위치 값을 더한 것은 최댓값 후보가 될 수 있다.  (왼쪽 위)

j-2번째 열에서 같은 행에 있는 값은 j-1번째 열의 대각선의 값에 이미 반영이 되므로, (왼쪽 아래) 다른 행에 있는 값에서 다른 행의 값을 더한 것만이 최댓값 후보가 될 수 있다. (오른쪽 아래)

 

위의 규칙을 코드로 구현하면 아래와 같다.

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

for _ in range(T):
    N=int(input().rstrip())
    stickers=[]
    for i in range(2):
        line=list(map(int, input().rstrip().split()))
        stickers.append(line)

    max_score=[[0 for _ in range(N)] for _ in range(2)]

    for j in range(N):
        for i in range(2):
            if j==0:
                max_score[i][j]=stickers[i][j]
            elif j==1:
                max_score[i][j]=max_score[1-i][j-1]+stickers[i][j]
            elif j>1:
                max_score[i][j]=max(max_score[1-i][j-1]+stickers[i][j], max_score[1-i][j-2]+stickers[i][j])

    print(max(max_score[0][N-1], max_score[1][N-1]))

탐색 문제에서 DP는 우선적으로 고려되어야 할 풀이 방법