BOJ [스티커]

문제

문제 보기

다음과 같이 점수가 부여된 스티커가 있다. 양옆, 위아래로 인접한 스티커를 동시에 선택할 수 없다. 스티커를 선택하여 획득할 수 있는 가장 큰 점수를 구하시오.

풀이

우선 나는 1차원 dp로 풀고자 했다. 아이디어는 이렇다. 각 dp마다 그 칸까지 진행했을 때 제일 많이 획득한 점수를 기록하고 마지막칸에서 선택한 스티커가 0(위)인지 1(아래)인지 기록한다.

위와 같은 상황이 있다하자. 첫번째 칸은 0을 선택한게 최대고 두번쨰 칸은 1을 선택한게 최대다. 그럼 3번째 칸은 두번째 칸 + 0 이거나 첫번째칸 + 1 이다. 하지만 문제가 생겼다.

다음과 같은 경우이다. 해당칸에서 0을 선택하던 1을 선택하던 두 개의 결과가 같은 경우이다. 내가 한 1차원 dp는 0,1중 하나를 선택하는 경우로만 진행해서 다음과 같은 상황을 처리하려면 재귀를 써야한다.

-> 쓴 결과 알고리즘은 맞는데 시간초과

그렇다면 어떻게 재귀를 안쓰고 풀 수 있을까?? 풀이를 보니까 2차원 dp를 사용했다. 그림을 보자.

stiker list와 같은 모양의 dp table을 만들어 사용한다. 각 칸의 스티커를 선택할 때 얻을 수 있는 가장 높은 점수를 table에 저장한다. 이 경우 앞서 언급한 문제가 발생해도 어차피 dp table상에 경우가 나뉘어져 저장되므로 따로 재귀처리를 안해줘도 된다.

코드

n = int(input())

for _ in range(n):
	m = int(input())

	stik = []
	for _ in range(2):
		stik.append(list(map(int,input().split())))

	dp = [[stik[0][0]],[stik[1][0]]]

	if len(stik[0]) == 1:
		print(max(dp[0][0],dp[1][0]))
		continue

	dp[0].append(stik[1][0]+stik[0][1])
	dp[1].append(stik[1][1]+stik[0][0])

	for i in range(2,len(stik[0])):
		dp[0].append(max(dp[1][i-1],max(dp[0][i-2],dp[1][i-2]))+stik[0][i])
		dp[1].append(max(dp[0][i-1],max(dp[0][i-2],dp[1][i-2]))+stik[1][i])

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