[Python] 프로그래머스. 스티커 모으기(2) (Level 4)

https://programmers.co.kr/learn/courses/30/lessons/12971

코딩테스트 연습 - 스티커 모으기(2) | 프로그래머스

DP문제. 점화식을 어떻게 세워야 하는지 도저히 모르겠어서 풀이를 참고했다.

 

table[i] = i번째 index까지의 배열에서 얻을 수 있는 최댓값이라고 정의하면

1) 만약 i-1번 index의 스티커를 뗐을 경우 = i번째 index 스티커는 뗄 수 없다. 즉 table[i-1]값 그대로

2) i-1번 스티커를 떼지 않았을 경우 = i-2번까지의 최댓값 + i번째 스티커의 값

이 된다.

 

즉 table[i] = max(table[i-1], table[i-2] + sticker[i]) 가 점화식이 된다.

 

여기서, 첫 번째 스티커를 떼느냐 아니냐가 마지막 index 스티커의 여부를 결정한다.

 

만약 첫 번째 스티커를 떼는 경우

table[0] = sticker[0], table[1] = sticker[0]이 되며, 마지막 index는 확인해서는 안 된다.

첫 번째 스티커를 떼지 않으면

table[0] = 0, table[1] = sticker[1]이 되며, 마지막 index까지 확인해야 한다.

 

코드로 정리하면