[백준] 9465번 : 스티커 (파이썬)

DP 문제 

https://www.acmicpc.net/problem/9465

9465번: 스티커

 

(1) 처음에 생각한 방식

 

한 스티커 기준으로 바로 인접한  ➡️⬇️⬆️⬅️ 방향에 있는 스티커는 붙힐 수 없다. 이 문제를 보자마자 dp로 풀어야겠다고 생각했다. dp는 bottom-up(작은 -> 큰) approach으로 table을 차근차근 채워나갈 것이기 때문에 ➡️⬇️⬆️⬅️ 방향 중 ⬆️⬅️ 방향의 스티커만 고려해서 피해 붙어주면 된다.

처음에 내가 좀 헤맸던게 문제를 제대로 안읽고 n x m 크기의 스티커인줄 알고 어떻게 접근해야할지 좀 어려웠던 것 같다. (2 x m 크기인거 확인한 순간 문제가 갑자기 너무 쉬워짐 ..)

 

*초기 문제접근 방식

일단 점화식 자체는 바로 생각이 안나서 dp 2차원 배열에 값을 채워나가며 점화식을 찾아보기로 했다.

1) dp[0][i]번째 배열 : max(-->에서 온 dp값, 바로 이전 dp값 - 바로 이전 스티커값) + 현재 스티커값

2) dp[1][i]번째 배열 : max(-->에서 온 dp값 / ↘️에서 온 dp값 ???, 바로 이전 dp값 - 바로 이전 스티커값) + 현재 스티커값

 

처음에는 정직하게 dp[0][i] ~ dp[1][i] 순서대로 테이블을 채워나갔지만, 문제에 봉착했다. 어떤 문제인지는 차근차근 설명해보겠다.

그림과 같이 보면 설명이 이해하기 쉬울거임.

1) dp[0][i]번째 배열 : -->에서 온 dp값이 선택되는 경우는 쉽게 말해 타일형식(퐁당퐁당) 더했을 때에 최댓값이 됨을 의미한다.

바로 이전 dp값 - 바로 이전 스티커값은 위처럼 퐁당퐁당 방식이 아니더라도 최댓값이 될 수 있는 경우이다. 이 값이 선택되는 경우는 이전에 저장된 dp값이 큰 경우이다. 해당 dp배열을 채울 때 현재 스티커는 무조건 붙힌다고 가정하고 채우기 때문에 바로 옆 스티커의 값은 포함될 수 없으므로 바로 이전 dp값 - 바로 이전 스티커값을 해주었다.

 

2) dp[1][i]번째 배열 : -->에서 온 dp값과 ↘️에서 온 dp값을 넣은 이유는 일단 ->과 ↓(바로 인접한 방향)의 스티커는 선택하지 못하기 때문에 -->와 ↘️에 저장해둔 dp값을 가져와야 한다고 생각했다.

하지만, 두번째 줄을 채울 때에 여기서 문제에 봉착했다. -->에서 온 dp값과 ↘️에서 온 dp값 중 뭘 어떻게 선택해야 하는 거지 ?

▪︎ max값을 선택해야 하나? 안된다. 그럼 포함 안되는 스티커 값이 있거나 원하는 값이 나오지 않음.

▪︎ -->에서 온 dp값과 ↘️에서 온 dp값을 더해야 하나? 안된다. 그럼 중복되는 스티커 값이 있다.

첫번째 줄을 채울 때처럼 점화식을 똑같이 해야 되는지 잠깐 고민했지만 이 역시 안된다. (그러면 위의 줄과 합쳐진 스티커 최댓값 자체를 구할수 없기 때문)

ex) 위의 그림에서 dp[1][3]번째 값을 구한다 했을 때, 노란색 형광펜 친 부분 스티커(50,50,100,10)이 선택돼 해당 dp값이 210이 나와야 한다. 하지만, -->와 ↘️ 방향 dp값 중 max를 취해 현재 스티커값을 더하거나 -->와 ↘️ 방향 dp값들을 모두 더한 뒤 현재 스티커 값을 더하는거 둘다 260이란 값이 나오기 때문에 둘다 안된다. 

 

그럼 어떻게 해야할까? 결론부터 말하면 dp 테이블을 채워나가는 순서를 바꿔보니 어떻게 해야할지 바로 감을 잡았다. 

 

(2) 내 코드 (성공)

# [DP] 실버 1 / 9465 스티커 
import sys
t = int(sys.stdin.readline())

def sticker(arr, b):
    for i in range(1, b):
        for j in range(2):
            if j == 0: dp[j][i] = max(dp[1][i-1], dp[0][i-1]-arr[0][i-1]) + arr[j][i] 
            else: dp[j][i] = max(dp[0][i-1], dp[1][i-1]-arr[1][i-1]) + arr[j][i]

while(t > 0):
    t-=1
    b = int(sys.stdin.readline())
    arr = []
    dp = [b * [0] for _ in range(2)]
    for _ in range(2):
        l = list(map(int, sys.stdin.readline().split()))
        arr.append(l)
    # print(arr)
    dp[0][0] = arr[0][0]
    dp[1][0] = arr[1][0]
    sticker(arr, b)
    print(max(dp[1][b-1], dp[0][b-1])) # 처음에 print(dp[1][b-1)해서 바로 틀렸다뜸.

 

dp 배열을 기존에는 row방향으로 순차적으로 채워나갔다면 col 방향으로 채워나가는 식으로 바꾸었다. 저렇게 물결모양으로 형광펜을 표시한 이유는 저렇게 물결 방향으로 dp값을 이용하여 테이블을 채워나가기 때문이다. 

 

점화식을 자세히 보면 max(물결방향 이전 dp값, 바로 이전 dp값 - 바로 이전 스티커값) + 현재 스티커값 이러한 형식이다.

(바로 이전 dp값 - 바로 이전 스티커값) 이부분 값을 사실 대각선 이전이전 방향에서 값을 들고 올 수도 있지만 위의 코드에 있는 점화식이 좀 더 직관적이라 생각해서 이렇게 짰다. (이것 때문에 시간초과 날까 조마조마했지만 안남 ㅎㅎ!)

(바로 이전 dp값 - 바로 이전 스티커값) 이부분은 사실 처음에 첫번째 줄 dp 테이블을 row방향으로 채워나갈 때 생각해낸 점화식이다.

 

이러고 제출했는데 사실 제출하자마자 틀렸다. 이유는 마지막에 최댓값이 무조건 dp[1][b-1]에서 나온다고 생각하여 이를 출력해주었는데 그 바로 위의 칸인 dp[0][b-1]에서 나올 수도 있기 때문이다. 

2
4
50 40 19 18
40 20 40 20
138
[[50, 80, 89, 138], [40, 70, 120, 109]]
4
40 40 39 40
40 40 40 40
160
[[40, 80, 119, 160], [40, 80, 120, 159]]

 

위와 같은 경우가 그 예시이다. 질문게시판에서 반례를 보고 dp 배열을 출력해본 뒤 비교 후에야 문제를 맞았지만, 이게 아니였다면 또 어디서 틀렸을까 한참을 고민했을 것이다... 이럴 경우를 대비해 사실 print(max(dp))를 때려박으면 되긴 하지만, 시간 좀이라도 아껴야지..하는 마음에 안썼다. 

 

느낀점 : dp 점화식이 생각 안날땐 테이블을 그리자 ..! 꼭 row방향으로만 테이블을 채워나가야한다고 생각하지말자.

 

*참고

https://jyeonnyang2.tistory.com/42

[Python] 백준 9465번: 스티커 풀이