[#9465] 스티커

RookieAND·2022년 5월 30일

DP 백준 코테

BaekJoon

목록 보기

7/42

❓ Question

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

📖 Before Start

오랜만에 동적 프로그래밍 문제를 한번 복습하는 차원에서 도전해보았다.

이번 문제는 점화식을 잘 세웠다고 생각했으나, 고려하지 않아도 될 조건까지 포함시켜 해결하지 못했다.
동적 프로그래밍에서 가장 핵심인 것은 점화식 을 잘 세우는 것인데, 아직은 갈 길이 멀어 보인다.

✒️ Design Algorithm

최댓값을 구하라는 문제는 높은 확률로 DP 를 활용하는 문제다.

2열로 고정된 2차원 배열에 스티커가 붙어 있고, 인접한 스티커는 선택할 수 없다는 제한 사항이 존재했다.
이 말인 즉슨 현재 선택한 스티커의 상하좌우 에 위치한 스티커들은 선택이 불가능하다는 의미였다.

따라서 i행 j열의 스티커를 선택할 경우 얻는 점수의 최댓값을 dp[i][j] 로 놓았고, 0행부터 끝까지
반복을 통해 점진적으로 최댓값의 누적 합을 메모이제이션에 저장하였다.

아래는 필자가 문제를 풀기 전 작성한 알고리즘 설계이다.

i행 j열에 해당되는 스티커를 골랐을 경우, 최댓값의 점화식을 어떻게 도출할 수 있을까?

만약 열의 갯수가 2 이하라면, 1열 0행 (dp[0][0]) 과 1열 1행 (dp[0][1]) 중에서 큰 값을 찾는다.
만약 열의 갯수가 3 이상이라면, i열 j행 (dp[i][j]) 의 최댓값은 not i열 j-1행 (dp[not i][j-1]) 과 i열 j-2행 (dp[not i][j-2]) 과 not i열 j-2행 (dp[i][j-2])의 최댓값 중에서 더 큰 값과 같다.

텍스트로 쓰려니 조금 어렵긴 하다. 하단의 코드를 보여주는 것이 훨씬 좋을 것 같다 (...)

💻 Making Own Code

❌ Wrong Code

import sys

read = sys.stdin.readline
T = int(read())
result = []
for _ in range(T):
    N = int(read())
    # dp[i][j] 는 i열 j행의 스티커를 선택할 경우, 얻는 점수의 최댓값을 저장
    dp = [[0] * N for _ in range(2)]
    sticker = [list(map(int, read().split())) for _ in range(2)]
    # 1행에 위치한 스티커 점수 값을 dp 에 초기화 시켜야 함.
    dp[0][0], dp[1][0] = sticker[0][0], sticker[1][0]

    for j in range(N):
        for i in range(2):
            # 점화식 1 : 행이 2 이상이라면 바로 이전 행을 택할 지, 2칸 전의 행을 택할지 정할 수 있다.
            # dp[i][j] = max(dp[not i][j - 1], max(dp[i][j - 2], dp[not i][j - 2])) + sticker[i][j]
            if j >= 2:
                dp[i][j] = max(dp[0 if i else 1][j - 1], max(dp[0][j - 2], dp[1][j - 2])) + sticker[i][j]
            # 점화식 2 : 행이 2 이하라면 이전 행에서 오직 인접하지 않은 스티커만을 선택해야 한다.
            # dp[i][j] = dp[not i][j - 1] + sticker[i][j]
            else:
                dp[i][j] = dp[0 if i else 1][j - 1] + sticker[i][j]

    result.append(max(dp[0][N-1], dp[1][N-1]))

print(*result, sep="\n")

하지만 고려하지 않아야 할 조건까지 모두 포함시킨 탓에 오답이 나고야 말았다.

j >= 2 조건에 해당되는 점화식에서는 j-2 행에 위치한 값을 고려했는데, 이것이 문제였다.
만약 i=0, j=2 행의 최댓값을 구한다고 가정한다면, 생각할 수 있는 경우는 총 2가지이다.

첫번째는 이전 행에 위치한 i=1, j=1 까지의 누적 합을 가져오는 것이고,
두번째는 그 전 행에 위치한 i=1, j=0 까지의 누적 합을 가져오는 것이다.

여기서 내가 실수한 것은i=0, j=0 에 대한 경우는 고려하지 않아도 된다는 것이었다.
그 이유는 i=1, j=1 까지의 누적합이 이미 i=0, j=0 의 누적합을 포함하고 있기 때문이다.

따라서 점화식은 dp[i][j] = max(dp[not i][j-1], dp[not i][j - 2]) + dp[i][j] 이다.

✅ Correct Code

import sys

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

for _ in range(T):
    N = int(read())
    # dp[i][j] 는 i열 j행의 스티커를 선택할 경우, 얻는 점수의 최댓값을 저장
    # 우선 각 열과 행에 놓인 스티커의 점수로 메모이제이션을 초기화 해야 함.
    dp = [list(map(int, read().split())) for _ in range(2)]
    # 1행에 위치한 스티커 점수 값은, 대각선에 위치한 이전 행의 점수를 더해주면 됨.
    # 단, 이는 N이 2 이상일 때만 가능하므로 조건식으로 체크를 해주어야 함
    if N > 1:
        dp[0][1] += dp[1][0]
        dp[1][1] += dp[0][0]

    # N이 3 이상일 때는 아래와 같은 점화식 진행이 가능하다.
    if N > 2:
        # 점화식 : 행이 2 이상이라면 바로 이전 행을 택할 지, 2칸 전의 행을 택할지 정할 수 있다.
        # dp[i][j] += max(dp[not i][j - 1], dp[not i][j - 2]))
        for i in range(2, N):
            dp[0][i] += max(dp[1][i - 1], dp[1][i - 2])
            dp[1][i] += max(dp[0][i - 1], dp[0][i - 2])

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