[백준9465] / 스티커 - DP

 

백준9465

 

 

푼 날짜 : 2024.09.14

푼 문제 : [9465] / 스티커

사용한 언어 : python

알고리즘 : DP

 

 

점화식 :

dp[0][i] = max(dp[1][i-1]+sticker[0][i], dp[1][i-2]+sticker[0][i]) 
dp[1][i] = max(dp[0][i-1]+sticker[1][i], dp[0][i-2]+sticker[1][i])

 

 

점화식 도출 과정은 다음과 같다.

아래와 같은 예시가 있을 때를 기준으로 계산해보겠다.

 

이는 sticker배열이다.

50	10	100	20	40
30	50	70	10	60

 

 

dp 배열은 초기값을 이렇게 설정해주었다.

50	40
30	100

 

 

초기값을 이렇게 설정한 이유는 다음과 같다.

스티커 한 장을 떼면, 그 스티커와 변을 공유하는 스티커는 모두 찢어져서 사용할 수 없게 된다.
즉, 뗀 스티커의 왼쪽, 오른쪽, 위, 아래에 있는 스티커는 사용할 수 없게 된다.

 

따라서 대각선이나 그 보다 멀리있는 스티커는 사용할 수 있기에 일단 가장 인접한 대각선을 기준으로 위처럼 채울 수 있다.

 

50	40	Here!
30	100

 

 

이번에는 이 위치에 있는 dp 배열을 채울 것이다. sticker 배열에서 해당 위치의 값은 100 이므로 이전 까지의 dp배열 중 가장 큰 값에 현재의 값을 더해서 dp배열을 채우면 된다.

 

 

 

다시 한 번 위의 조건을 확인해보면, 인접한 상하좌우의 스티커는 사용할 수 없다. 따라서 대각선이나 조금 더 거리가 있는 것을 기준으로 판단한다.

 

50	40	? + 100
30	100

 

? 에 들어갈 수 있는 값은 30 과 100 둘 중 하나이다. 이 값들은 상하좌우의 값이 아니며, 이전 값들의 계산값을 포함하고 있기 때문이다.

당연히 우리는 값을 최대로 만들어야 하기 때문에 100을 선택할 것이며 해당 위치는 

 

50	40	200
30	100

 

이렇게 바뀐다.

 

 

 

dp 테이블을 이러한 기준으로 쭉쭉 채우다 보면

 

50	40	200	140	250
30	100	120	210

 

이렇게 채울 수 있다.

 

마지막 값도 역시 sticker에서 해당 위치는 60이라는 값을 가지고 있으며 200 과 140을 비교했을 때 200이 더 크므로 260으로 채워주면 된다.

 

50	40	200	140	250
30	100	120	210	200+60

 

 

최종적으로 마지막 값들 중 큰 값을 출력해주면 된다.

 

 

 

코드 :

import sys

T = int(sys.stdin.readline())
for _ in range(T):
    n = int(sys.stdin.readline())
    dp = [[0 for _ in range(n)] for _ in range(2)]
    
    sticker = []
    for _ in range(2):
        lst = list(map(int, sys.stdin.readline().split()))
        sticker.append(lst)
    
    # n이 1일 땐 dp배열의 초기값 설정에서 인덱스 에러가 나기 때문에 두 값을 바로 비교하여 프린트한다.
    if n == 1:
        print(max(sticker[0][0], sticker[1][0]))
    else: 
        dp[0][0] = sticker[0][0]
        dp[1][0] = sticker[1][0]
        dp[0][1] = dp[1][0] + sticker[0][1]
        dp[1][1] = dp[0][0] + sticker[1][1]

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

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

 

 

항상 코딩테스트에서는 범위를 잘 확인해야 한다. 

n (1 ≤ n ≤ 100,000) 이라는 조건을 제대로 확인하지 않고 점화식을 찾아 문제를 풀다가 처음 제출 했을 때 IndexError를 만났다.

초기 dp 배열은 n이 2이상 이어야 채워지기 때문에 n이 1인 경우엔 인덱스 에러가 날 수 밖에 없다.

 

따라서 조건문으로 나누어 주었다.

 

실수하지 않도록 항상 꼭 다양한 케이스를 고려하고 생각하며, 범위를 잘 확인하자!

오늘도 1커밋 성공! \_へ(▭-▭)✨