문제
상근이의 여동생 상냥이는 문방구에서 스티커 2n개를 구매했다. 스티커는 그림 (a)와 같이 2행 n열로 배치되어 있다. 상냥이는 스티커를 이용해 책상을 꾸미려고 한다.
상냥이가 구매한 스티커의 품질은 매우 좋지 않다. 스티커 한 장을 떼면, 그 스티커와 변을 공유하는 스티커는 모두 찢어져서 사용할 수 없게 된다. 즉, 뗀 스티커의 왼쪽, 오른쪽, 위, 아래에 있는 스티커는 사용할 수 없게 된다.
모든 스티커를 붙일 수 없게된 상냥이는 각 스티커에 점수를 매기고, 점수의 합이 최대가 되게 스티커를 떼어내려고 한다. 먼저, 그림 (b)와 같이 각 스티커에 점수를 매겼다. 상냥이가 뗄 수 있는 스티커의 점수의 최댓값을 구하는 프로그램을 작성하시오. 즉, 2n개의 스티커 중에서 점수의 합이 최대가 되면서 서로 변을 공유 하지 않는 스티커 집합을 구해야 한다.
위의 그림의 경우에 점수가 50, 50, 100, 60인 스티커를 고르면, 점수는 260이 되고 이 것이 최대 점수이다. 가장 높은 점수를 가지는 두 스티커 (100과 70)은 변을 공유하기 때문에, 동시에 뗄 수 없다.
풀이
- 테이블 정의
dp[i][j] = dp[i][j] 번째까지 선택했을 때 최대값 - 초기값 설정
아무것도 고르지 않았을 때의 값은 0이다. 순회하면서 스티커 테이블 자체를 업데이트 할 예정이기에 스티커를 받아오면서 0을 스티커테이블 앞에 넣어준다. - 점화식
i가 0이라고 가정
stickers[i][j] = max(stickers[1][j-1] + stickers[i][j], stickers[i][j-1])
전 스티커를 사용하고 지금 스티커를 떼려고 한다는 가정하에 생각해보면 바로 전 column값의 스티커는 사용이 불가능하다.
설명하기 편하게 현재 인덱스를 2, 3로 놓고 생각해봤을 때 테이블 상에서 바로 옆인 2, 2값을 사용하여 스티커를 붙였다면 2, 3의 사용은 불가능하다.
반대로 1, 2를 사용했다면 2, 3에 있는 스티커를 붙일 수가 있다.
따라서 2, 3에서의 최대값은 왼쪽 스티커를 사용하고 지금 스티커를 사용하지 않은 값과 왼쪽 아래 스티커를 붙이고 지금의 스티커를 붙인 값 두 값의 최대값이 된다.
풀이에서 주의할 점은 칼럼을 기준으로 순회하면 업데이트되지 않은 로우값에 접근할 수 있기 때문에 로우 칼럼순으로 순회하는 것이 아니라 칼럼 로우 순으로 순회해야한다는 것이다.
import sys
input = sys.stdin.readline
T = int(input())
for _ in range(T):
N = int(input())
stickers = [[0] + list(map(int, input().split())) for _ in range(2)]
for col in range(1, N+1):
for row in range(2):
stickers[row][col] = max(stickers[not row][col-1] + stickers[row][col], stickers[row][col-1])
print(max(stickers[0][N], stickers[1][N]))피드백
문제에 투자하는 시간이 조금 더 줄었으면 좋겠다. dp문제는 내일부터 1시간 안에 풀기를 시도해봐야겠다.
