[백준 BOJ_9465] 스티커 Python 풀이

출처: 백준 온라인 저지

문제

풀이

동적계획법으로 풀었습니다.

cache를 따로 만들어주지 않고 입력받은 stickers의 값을 갱신하며 풀어주었습니다.

현재 위치의 스티커를 고른다는 전제하에 고를 수 있는 스티커의 조건은 두 가지의 경우의 수로 나뉩니다.

1. 현재 스티커의 위치에서 왼쪽 대각선에 있는 스티커를 고르는 경우
2. 현재 스티커의 위치에서 왼쪽 대각선에 있는 스티커를 고르지 않는 경우

바로 왼쪽이나 바로 위, 또는 아래의 스티커는 고를 수 없기에 가능한 선택지는 왼쪽 대각선밖에 없습니다. 하지만 그 왼쪽 대각선에 있는 스티커를 고르지 않는 경우도 확인해주어야 합니다. 왼쪽 대각선의 스티커를 고르지 않는 경우에도 그 왼쪽과 위, 또는 아래에 있는 스티커를 고려하주어야 하는 데 위, 또는 아래에 있는 스티커는 현 위치의 스티커의 왼쪽 스티커가 되므로 고를 수 없습니다. 아래의 예시를 들어 설명해보겠습니다.

@ = 현재 위치
       @
| 50 | 10 | 100 | 20 | 40 |
| 30 | 50 | 70  | 10 | 60 |

위의 스티커에서 우선 두 번째 열에서는 왼쪽 대각선을 선택할 수 밖에 없습니다. 선택하게 되면 다음과 같이 됩니다.

@ = 현재 위치
             @
| 50 | 40  | 100 | 20 | 40 |
| 30 | 100 | 70  | 10 | 60 |

세 번째 열에서는 스티커의 값이 100인 첫 번째 행 스티커부터 확인해주겠습니다. 우선 왼쪽 대각선의 값은 100이고, 왼쪽 대각선의 100을 고르지 않았을 때는 100과 맞닿아 있는 왼쪽의 30과, 위쪽의 40중에 고려해주어야 하는데, 40은 현재의 위치의 스티커인 100과 맞닿아 있어 고를 수 없습니다. 그러므로 우리는 왼쪽 대각선의 스티커를 고르지 않을 경우에는 왼쪽 대각선의 스티커의 왼쪽 스티커만 고려해주면 됩니다. 100과 30중 큰 값을 현재의 스티커의 값에 더해주면 됩니다. 두 번째 행도 같은 방법으로 선택해주면 다음과 같이 됩니다.

| 50 | 40  | 200 | 20 | 40 |
| 30 | 100 | 120 | 10 | 60 |

두 번째 행의 경우는 대각선 스티커 40보다 그 왼쪽의 50점의 스티커가 점수가 높으므로 70에 50을 더해준 120이 됩니다. 동일한 방법으로 끝까지 채워주면 다음과 같이 됩니다.

| 50 | 40  | 200 | 140 | 250 |
| 30 | 100 | 120 | 210 | 260 |

마지막에는 마지막 열의 두 값을 비교하여 더 큰 값을 출력해주면 됩니다.

코드

T = int(input())

for _ in range(T):
  N = int(input())
  stickers = [list(map(int, input().split())) for _ in range(2)]
  
  for i in range(1, N):
    if i == 1:
      stickers[0][i] += stickers[1][i - 1]
      stickers[1][i] += stickers[0][i - 1]
    else:
      stickers[0][i] += max(stickers[1][i - 1], stickers[1][i - 2])
      stickers[1][i] += max(stickers[0][i - 1], stickers[0][i - 2])
  print(max(stickers[0][N - 1], stickers[1][N - 1]))