[BOJ][Python]9465번 풀이

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

9465번: 스티커

import sys
ssr = sys.stdin.readline

t = int(ssr())
for _ in range(t):
    n = int(ssr())
    sticker = [list(map(int, ssr().split())) for _ in range(2)]
    dp = [[0 for _ in range(n)] for _ in range(2)]
    dp[0][0], dp[1][0] = sticker[0][0], sticker[1][0]
    if n > 1:
        dp[0][1], dp[1][1] = dp[1][0]+sticker[0][1], dp[0][0]+sticker[1][1]
    for i in range(2,n):
        dp[0][i] = max(dp[1][i-1], dp[1][i-2])+sticker[0][i]
        dp[1][i] = max(dp[0][i-1], dp[0][i-2])+sticker[1][i]
    print(max(dp[0][-1], dp[1][-1]))

정말 dp는 dp스러운 생각을 얼마나 잘할 수 있는지로 갈리는 것 같습니다. 최근에 클래스 3을 진행하면서 dp를 꽤 오랜시간 안풀었더니 정말 정답에 접근하는데에 시간이 너무 오래걸려요.

 

문제 풀이는 당연히 dp입니다(처음에는 bfs인가? 하는 생각을 했었죠. 이제 뭐만하면 그래프 탐색부터 생각나네요). 해당 문제는 내가 고른 스티커의 상하좌우를 사용할 수 없게된다는 점이 dp로 이끄는 키포인트입니다. 사실 저번 문제와 제약의 타입이 비슷하죠(바로 아래, 아니면 아래 오른쪽만 선택할 수 있던 최댓값 문제). 그래서 처음부터 그냥 끝까지 가면서 max 구해야지하고 생각을 했어야 했는데 뭔가 효율적으로 풀어보겠다고 나서다가 시간만 잔뜩 걸리고 오히려 풀이의 핵심에 접근을 못했던 것 같습니다. 해당 문제는 n이 1일 때, 2일 때, 3일 때로 처음부터 확장해나가는 쪽이 식을 세우기 편한 문제입니다. n이 1이라면 원소는 두 개 뿐이니 둘 중에 큰 녀석이 답이겠죠. 2라면 00 + 11, 10+01 중에서 큰 쪽이 정답일 겁니다. 이걸 위에서 나온 방식대로 써본다면  dp[0][1], dp[1][1] = dp[1][0]+sticker[0][1], dp[0][0]+sticker[1][1] 이 되겠죠(dp[1][0] = sticker[1][0], dp[0][0] = sticker[0][0]). 그 뒤의 인덱스 부터는 형태가 좀 달라지긴 합니다만 사실 입력 예시에서 힌트를 좀 주긴 했습니다(예시 1의 케이스 1에서 100 다음 10 40을 선택하는게 아닌 60을 선택하는 것). 그래도 풀어서 보죠. n=3이라고 한다면 스티커를 선택할 수 있는 경우의 수는 00+11+02, 10+01+22, 00+22, 10+02 이렇게 4개일 겁니다. 그걸 2대신 i를 대입해서 최댓값을 구한다는 의미의 코드로 옮겨보면 반복문안에 있는 코드가 될 것입니다. 참 이렇게 보면 쉬운데 이상하게 접근법이 잘 안떠오른단 말이죠.