9465번: 스티커 (2차원 DP)

9465번: 스티커

이 문제를 봤을 때 단순 DP 문제인 것 같아서, 관찰을 해보았다. 스티커를 뗀 부분을 동그라미, 같이 떼어진 부분을 세모라고 한다면(동그라미에 주목) 다음과 같이 i-1번째의 열에서 스티커를 뗀 경우(case1)과 i-1번째에서 스티커를 떼지 않은 경우(case2)로 나누어볼 수 있었다.

이때 i-1번째에서 스티커를 땔 때는 i-1번째 열에서 위에 있는 스티커를 떼었는지 아니면 아래있는 스티커를 떼었는지에 따라 i번째 열에서 뗄 스티커가 결정되고, i-1번째에서 스티커를 떼지않을 때에는 i번째는 위,아래 중 어떤 것을 떼어도 상관없으니까 이 중 값이 큰 것을 선택하면 되겠다고 생각이 들었다. 여기서 이제 dp[i] = max(case1,case2)로 구하면 되겠구나! 하고 바로 구현에 시도해보았다.  

 

case1: i-1번째 열에서 스티커를 뗀 경우, case2: i-1번째 열에서 스티커를 떼지 않은 경우

그 결과 case2는 case2 = d[i-2] + max(graph[0][i],graph[1][i]) 로 구할 수 있었다. 하지만 문제는 case1 이었다. 

위에서 말했다시피 i-1번째에서 어떤 위치의 스티커를 떼었는지를 알아야 이를 구현할 수 있는데 도저히 1차원 dp리스트에서는 이를 알 방법이 없었다. 따라서 여기서 2차원 DP 테이블을 도입해야 하겠구나를 느낄 수 있었다!

DP 테이블의 i번째 열을 보면, dp[0][i],dp[1][i] 값이 있을텐데 이 값들이 무엇을 의미하는지를 정의할 필요가 있다. 

dp[1][4]을 왼쪽부터 4번째 열까지 스티커를 떼어내는데 4번째 열의 1번째 행의 스티커를 떼어낼 때 최댓값으로 정의를 했다. 이에 맞추어 graph와 table을 그려보았다.

0 번째 열은 graph와 똑같이 ( dp[0,1] = graph[0,1] ) 1번째 열은 대각선으로 더한 값을 넣어주면 된다(dp[1,1] = graph[0][0] + graph[1][1]) 

 

위에가 문제에서 제시하는 graph이고, 밑에가 2차원 리스트 형태의 DP table이다.

이때 2이상의 i에 대해서 맨 처음에 접근한 방식을 그대로 적용해보자.

 

dp[0][i-2]	dp[0][i-1]	dp[0][i]
dp[1][i-2]	dp[i][i-1]	dp[1][i]

 

dp[0][i]를 구하기 위해선 처음에 case1, case2를 적용하면 된다. 

case2는 i-1번째 열에서 스티커를 떼지 않을 때이니까, case2 = max(dp[0][i-1],dp[0][i-2]) + graph[0][i] 이고

case1에서는 case1 = dp[i][i-1] + graph[0][i]로 구할 수 있고, dp[0][i] = max(case1,case2) 로 구할 수 있다. 

마찬가지로 dp[1][i]에도 적용해 top-down 방식으로 DP를 구현하면 다음과 같다.  

 

t = int(input())
for k in range(t):
    n = int(input())
    graph = []
    for i in range(2): # 2차원 리스트로 행,열을 나타냄
        graph.append(list(map(int,input().split())))
    # 2차원 리스트 선언할 때 잘 해줘야 한다.
    # 처음에 dp = [[0]*100001]*2 로 했었는데 이러면 복제되서 안된다.
    dp = [[0]*100001,[0]*100001]
    dp[0][0],dp[1][0] = graph[0][0],graph[1][0]
    dp[0][1],dp[1][1] = graph[1][0] + graph[0][1], graph[0][0] + graph[1][1]
 
    for i in range(2,n):
        dp[0][i] = max(max(dp[0][i-2],dp[1][i-2]) + graph[0][i], dp[1][i-1] + graph[0][i])
        dp[1][i] = max(max(dp[0][i-2],dp[1][i-2]) + graph[1][i], dp[0][i-1] + graph[1][i])
    print(max(dp[0][n-1],dp[1][n-1]))

 

 

 

PS. 이런 유형의 2차원 DP 문제는 아직 낯설어서 좀 더 연습해야겠다. 그리고 2차원 리스트를 선언할 때 조심해야지..