DP 새로운 유형..??

#9465번 스티커 https://www.acmicpc.net/problem/9465

9465번: 스티커

 

기존의 DP문제와는 약간 다른 모습을 보여서 신기했다.

 

기존의 DP는 특정 조건에 맞춰서 값을 새로 추가해나가는 형태였는데

이 문제는 주어진 값들 (리스트)을 갱신해 나가는 형태로 진행하는게 효율적이었다.

 

풀이

1) 스티커를 떼면 상하좌우 스티커를 사용할 수 없다.

2) 그런 상황에서의 스티커 점수의 최댓값

 

상하좌우에 위치한 값을 선택할 수가 없다

-> 대각선 상에 위치한 값들만 사용할 수 있다.

 

 예제를 한번 보자. 50을 선택할 경우에 두 번째로 선택할 수 있는 값을 보면, 3개라고 생각할 수 있지만

 

사실 2개다

 

 

 100을 선택할 경우에는 50을 선택할 수도 있기 때문이다.

 

이를 조금 더 일반화 시켜본다면

2차원 배열로 들어오는 입력값에서 하나를 선택한 후 nums[0][0]

다음으로 선택할 수 있는 값들은 nums[1][1], nums[1][2] 가 된다.

 

 

이제 상황 분석은 얼추 끝났다. 다음은 DP의 핵심개념인 메모이제이션. 이전에 저장한 값들을 어떻게 활용하면서 다음 값을 갱신해 나갈지에 대한 고민이 필요하다.

 

정답은 이렇다.

 

1) 왼쪽에서 시작한다. (Bottom-Up 방식이라고도 하는데 난 아직 잘 쓰지 않는다.)

2) 첫 번째 열 부터 시작하고, 다음 두 번째 열을 진행한다.

3) [0,0] 과 [0,1]은 제일 왼쪽 값이므로 제 값을 유지한다.

4) 2행으로 진행. [0,1]의 경우에는 왼쪽에 있는 값들 중 함께 선택될 수 있는 값이 [1,0]에 위치한 30 뿐이다.

5) [0,1]의 값에 30을 더해준다. 또 2열의 2행 [1,1]에도 같은 방식의 연산을 적용한다.

 

6) 3행으로 간다. [0,2]의 경우에는 선택할 수 있는 경우의 수가 두가지이다.

7) [1,0] 과 [1,1]. [1,1]은 [0,0]과 함께 선택될 수 있기 때문에 갱신되어있다. ( [1,1] = [0,0] + [1,1] )

8) 이 두가지 경우 중 더 큰 값을 더해 [0,2]를 갱신해준다.

9) 같은 방식으로 2열에도 적용한다.

 

이런 방식으로 행의 개수만큼 (n만큼) 루프를 돌려주면 된다.

그럴 경우에 마지막 행에 두 가지 값이 나오고, 그 두 값 중 더 큰 값이 정답이 된다.

 

import sys
for i in range(int(sys.stdin.readline())):
    n = int(sys.stdin.readline())

    nums1 = list(map(int, sys.stdin.readline().split()))
    nums2 = list(map(int, sys.stdin.readline().split()))
    nums = [nums1] + [nums2]

    for c in range(1, n):
        nums[0][c] += nums[1][c -
                              1] if c < 2 else max(nums[1][c-1], nums[1][c-2])
        nums[1][c] += nums[0][c -
                              1] if c < 2 else max(nums[0][c-1], nums[0][c-2])
        
    print(max(nums[0][n-1], nums[1][n-1]))

시간 초과가 나오길래 sys.stdin.readline()을 사용했다. 근데 max값을 구할 때 두 값을 비교하는게 아니라 이전 리스트 전체를 비교하게 만들었던게 원인이었던 것 같다. 스티커의 최대 길이가 십만이기 때문에 최악의 경우에는 10만줄의 리스트를 연달아 비교해 max값을 찾아야 하기 때문이다.

 

조금 더 직관적으로 이해할 수 있게 출력값을 조절해봤다. 이해에 도움이 됐길 바란다.