💻 백준 9465번: 스티커
- 문제 링크: https://www.acmicpc.net/problem/9465
- 알고리즘 분류: 다이나믹 프로그래밍
문제 소개 🧐
상근이의 여동생 상냥이는 문방구에서 스티커 2n개를 구매했다. 스티커는 2행 n열로 배치되어 있다. 스티커 한 장을 떼면, 그 스티커와 변을 공유하는 스티커는 모두 찢어져서 사용할 수 없게 된다.
각 스티커에 점수를 매기고, 점수의 합이 최대가 되게 스티커를 떼어내려고 한다. 2n개의 스티커 중에서 점수의 합이 최대가 되면서 서로 변을 공유 하지 않는 스티커 집합을 구해야 한다.
입력 📝
첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 점수이다.
제한 🚫
- 시간 제한: 1초
- 메모리 제한: 256MB
- 1 ≤ n ≤ 100,000
- 스티커의 점수는 0보다 크거나 같고, 100보다 작거나 같은 정수이다.
출력 📤
각 테스트 케이스 마다, 2n개의 스티커 중에서 두 변을 공유하지 않는 스티커 점수의 최댓값을 출력한다.
나의 풀이 과정 🌊
아이디어
시간 제한이 1초로 빡빡하기 때문에 DP(다이나믹 프로그래밍)를 사용하여 문제를 풀어야겠다고 생각했다.
dp[0][i]는 0행의 i번째 스티커를 선택했을 때의 최대 점수, dp[1][i]는 1행의 i번째 스티커를 선택했을 때의 최대 점수로 정의했다.
점화식은 다음과 같이 세울 수 있다.
dp[0][i]를 선택하려면, 이전 열(i-1)에서는 1행의 스티커를 선택했어야 한다.dp[1][i]를 선택하려면, 이전 열(i-1)에서는 0행의 스티커를 선택했어야 한다.
하지만, 이전 열의 스티커를 선택하지 않는 경우도 고려해야 한다. 즉, i-2열의 스티커를 선택하는 경우이다.
따라서 최종적인 점화식은 다음과 같다.
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]
최종 코드
import sys
T = int(sys.stdin.readline().rstrip())
for _ in range(T):
n = int(sys.stdin.readline().rstrip())
sticker = [list(map(int, sys.stdin.readline().split())) for _ in range(2)]
if n > 1:
# dp 테이블 초기화
sticker[0][1] += sticker[1][0]
sticker[1][1] += sticker[0][0]
for i in range(2, n):
sticker[0][i] += max(sticker[1][i-1], sticker[1][i-2])
sticker[1][i] += max(sticker[0][i-1], sticker[0][i-2])
print(max(sticker[0][n-1], sticker[1][n-1]))
Result: 성공! ✅
배운 점 및 느낀 점 ✍️
- DP 문제를 풀 때, 점화식을 세우는 것이 가장 중요하다는 것을 다시 한번 느꼈다.
dp[i]를 정의할 때, 어떤 상태를 저장할 것인지 명확하게 해야 한다.- 이번 문제에서는
dp[0][i]와dp[1][i]를 각각 0행과 1행의 i번째 스티커를 뗐을 때의 최대 점수로 정의해야 했다. - 점화식을 세울 때, 현재 상태가 이전 상태들에 어떻게 영향을 받는지 파악하는 것이 중요하다.
dp[0][i]는dp[0][i-1](i-1번째 스티커를 떼지 않음)과dp[1][i-1] + sticker[0][i-1](i-1번째 스티커를 떼고, 현재 스티커를 뗌) 중 더 큰 값으로 결정된다.dp[1][i]도 마찬가지로dp[1][i-1]과dp[0][i-1] + sticker[1][i-1]중 더 큰 값으로 결정된다.- 이렇게 점화식을 세우고 나니, 코드를 작성하는 것은 어렵지 않았다.
- DP 문제에 대한 감을 조금씩 찾아가는 것 같다.