코드
def solution(sticker):
answer = 0
if len(sticker) == 1:
return sticker[0]
# Case1) 0번 뜯음
dp = [0 for _ in range(len(sticker))]
dp[0], dp[1] = sticker[0], sticker[0]
for i in range(2, len(sticker)-1):
dp[i] = max(dp[i-2] + sticker[i], dp[i-1])
answer = dp[-2]
# Case2) 1번 뜯음(0번 못 뜯음)
dp.clear()
dp = [0 for _ in range(len(sticker))]
dp[0], dp[1] = 0, sticker[1]
for i in range(2, len(sticker)):
dp[i] = max(dp[i-2] + sticker[i], dp[i-1])
return max(answer, dp[-1])
처음에는 DFS로 하면 되지 않을까? 싶었는데 문제의 조건에서 스티커 배열의 길이가 최대 100,000이라 해서 바로 그 생각 버렸다.
그리고 떠오른게 다이나믹 프로그래밍이었다. 점화식을 세워서 풀 수 있는 문제인거 같아서 생각해보니 본인 차례에서 선택할 수 있는 선택지는 본인 2개 이전의 스티커를 뜯고 본인도 뜯느냐, 아니면 본인 바로 이전의 스티커를 뜯고 본인은 못 뜯느냐 2가지뿐이다. 따라서 점화식은 다음과 같다.
dp[i] = max(dp[i-2] + sticker[i], dp[i-1])
그런데 이 때 주의할 점은 이 스티커는 원형으로 연결되어 있다. 하지만 주어진 배열은 1차원 배열이므로 0번 스티커를 뜯느냐, 1번 스티커를 뜯느냐 2가지 경우로 나누어서 풀이하였다.
- 0번 스티커를 뜯는경우, 1번 스티커를 못 뜯으므로 dp[1]에도 sticker[0]의 값을 저장해주고 시작하면 된다. 그리고 마지막 스티커(n-1)는 뜯을 수 없을 것이므로 dp[-2]가 0번 스티커를 뜯을 경우의 최대값이다.
- 1번 스티커를 뜯는 경우, 0번 스티커는 못 뜯으므로 dp[0]에는 0을 저장해주고 시작한다. 이 경우는 마지막 스티커를 뜯을 수 있으므로 dp[-1]이 최대값이다.
정답은 이 두 경우 중 큰 값을 출력해주면 된다.
'문제풀이 > DP' 카테고리의 다른 글
[Python/파이썬] 프로그래머스 등굣길 (0) | 2022.10.26 |
---|---|
[Python/파이썬] 프로그래머스 피보나치 수 (0) | 2022.10.20 |
[Python/파이썬] 프로그래머스 정수 삼각형 (0) | 2022.10.10 |
[Python/파이썬] 백준 11049번 행렬 곱셈 순서 (1) | 2022.10.05 |
[Python/파이썬] 백준 7579번 앱 (0) | 2022.09.29 |