프로그래머스_스티커 모으기(2)

문제

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

코딩테스트 연습 - 스티커 모으기(2)

 

풀이

N개의 스티커가 원형으로 연결되어 있으므로 (1) 첫번째 스티커가 쓰이는 경우와 (2) 첫번째 스티커가 쓰이지 않는 경우로 나누어서 생각해야 한다.

 

(1) 첫번째 스티커가 쓰이는 경우

dp에는 0번째 스티커를 사용하고 1번째 스티커를 사용하지 않은 경우 i까지의 최대 값을 저장한다.

• dp[i-1] : i번째 스티커를 사용하지 않음
• dp[i-2]+dp[i] : i-2번째 스티커와 i번째 스티커를 사용함
• dp[0] = sticker[0] : 0번째 스티커를 사용
• dp[1] = sticker[0] : 1번째 스티커를 사용하지 않음
• range(2, len(sticker)-1) : 0번째 스티커를 사용했으므로, 마지막 스티커는 사용 할 수 없음

sticker	14	6	5	11	3	9	2	10
dp[i-1]			14	19	25	25	34
dp[i-2] +dp[i]			14+5	14+11	19+3	25+9	25+2
dp	14	14	19	25	25	34	34

 

(2) 첫번째 스티커가 쓰이지 않는 경우

dp에는 0번째 스티커를 사용하고 1번째 스티커를 사용하지 않은 경우 i까지의 최대 값을 저장한다.

• dp[i-1] : i번째 스티커를 사용하지 않음
• dp[i-2]+dp[i] : i-2번째 스티커와 i번째 스티커를 사용함
• dp[0] = 0 : 0번째 스티커를 사용하지 않음
• dp[1] = sticker[1] : 1번째 스티커를 사용할 수 있음
• range(2, len(sticker)) : 0번째 스티커를 사용하지 않았으므로, 마지막 스티커를 사용할 수 있음

sticker	14	6	5	11	3	9	2	10
dp[i-1]			6	6	17	17	26	26
dp[i-2] +dp[i]			0+6	6+11	6+3	17+9	17+2	26+10
dp	0	6	6	17	17	26	26	36

 

(3) 최대값

(1) 첫번째 스티커가 쓰이는 경우에는 dp[-2], (2) 첫번째 스티커가 쓰이지 않는 경우에는 dp[-1]에 최댓값을 가지고 있다. 두 원소를 비교하면 답을 얻을 수 있다.

코드

def solution(sticker):
    size = len(sticker)
    if size<2 : return sticker[0]

    # (1) sticker[0]을 사용 o
    dp1 = [n for n in sticker]
    dp1[1] = sticker[0]
    for i in range(2, size-1) : 
        dp1[i] = max(dp1[i-1], dp1[i-2]+dp1[i])

    # (2) sticker[0]을 사용 x
    dp2 = [n for n in sticker]
    dp2[0] = 0
    for i in range(2, size) : 
        dp2[i] = max(dp2[i-1], dp2[i-2]+dp2[i])

    return max(dp1[-2], dp2[-1])