[백준9465] / 스티커 - DP
푼 날짜 : 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커밋 성공! \_へ(▭-▭)✨