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

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

9465번: 스티커

dp 알고리즘으로 분류된 문제이다.

점화식을 찾는데 다른 dp 문제보다 시간이 조금 더 걸렸지만, 어려움 없이 잘 풀었다.

 

풀이

---

각 단계별로 어떻게 해야 최대로 스티커 점수를 얻을 수 있는지 점화식을 찾아야 한다.

위 그림은 스티커를 선택하는 예시이다.

A를 기준으로 E와 F를 선택할 수 있는 경우의 수이다.

E에서 H로 가는 선은 점화식을 세울 때 고려하지 않아도 된다.

B를 기준으로 E와 F를 선택할 수 있는 경우가 두 개지 있을 것이다.

이 정보를 토대로 점화식을 세워봤다.

 

dp[0][0] = arr[0][0]
dp[1][0] = arr[1][0]

dp[0][1] = dp[1][0] + arr[0][1]
dp[1][1] = dp[0][0] + arr[1][1]

for i in range(2, n):
    dp[0][i] = max(dp[1][i-1] + arr[0][i], dp[1][i-2] + arr[0][i])
    dp[1][i] = max(dp[0][i-1] + arr[1][i], dp[0][i-2] + arr[1][i])

각 스테이지마다 위, 아래가 선택되기 때문에 dp도 2xn 배열로 만들었다.

이전의 사진에서 E가 선택될 경우는
1) A -> D -> E
2) B -> E

그렇다면 G가 설택 될 경우는
1) A -> D -> G
2) B -> C -> F -> G

그렇다면 n번째 위 점이 선택 될 경우를 풀어서 적어보면
1) n - 1번째 아래 점을 선택하거나
2) n - 2번째 아래 점을 선택하는 경우이다.

위와 같은 규칙을 적용해 코드를 작성하면 문제를 풀 수 있다!

- 정답 코드

import sys
input=sys.stdin.readline


if __name__ == "__main__":
    for test in range(int(input())):
        n = int(input())
        arr = [[0]*n,[0]*n]
        dp = [[0]*n,[0]*n]
        for idx, var in enumerate(map(int,input().split())):
            arr[0][idx] = var
        for idx, var in enumerate(map(int,input().split())):
            arr[1][idx] = var

        dp[0][0] = arr[0][0]
        dp[1][0] = arr[1][0]

        dp[0][1] = dp[1][0] + arr[0][1]
        dp[1][1] = dp[0][0] + arr[1][1]

        for i in range(2, n):
            dp[0][i] = max(dp[1][i-1] + arr[0][i], dp[1][i-2] + arr[0][i])
            dp[1][i] = max(dp[0][i-1] + arr[1][i], dp[0][i-2] + arr[1][i])
        print(max(dp[0][n-1], dp[1][n-1]))

 

- 문제의 특성을 이용하여 불필요한 메모리를 최적화 한 코드

import sys
input=sys.stdin.readline


if __name__ == "__main__":
    for test in range(int(input())):
        n = int(input())
        arr = [[0]*100000,[0]*100000]

        for idx, var in enumerate(map(int,input().split())):
            arr[0][idx] = var
        for idx, var in enumerate(map(int,input().split())):
            arr[1][idx] = var

        arr[0][1] += arr[1][0]
        arr[1][1] += arr[0][0]

        for i in range(2, n):
            arr[0][i] += max(arr[1][i-1], arr[1][i-2])
            arr[1][i] += max(arr[0][i-1], arr[0][i-2])
        print(max(arr[0][n-1], arr[1][n-1]))

 

 

결과

---

이번 문제도 점화식을 정확하게 구현하여 한 번만에 맞췄다.

한 번의 시도만에 문제를 맞힌다는 건 정말 뿌듯한 것 같다. ㅋㅋ