[프로그래머스/Python] Level 3_스티커 모으기(2)

📌문제 유형

DP

 

📌문제

프로그래머스

 

📌나의 문제풀이

- 실패

• len(sticker) 짝수 : 인덱스 홀수, 인덱스 짝수 더해서 큰 값
• len(sticker)  홀수 : 시작점 선정 + len(sticker) 짝수 방법 반복

-> 다른 숫자 대비, 엄청 큰 숫자가 있는 경우 안될 것이라는 판단

import copy

def solution(sticker):
    answer = 0
    tmp, tmp_0, tmp_1 = 0, 0, 0
    
    # 짝수 - 최대 5만번
    if len(sticker) % 2 == 0:
        for i in range(0,len(sticker),2):
            tmp_0 += sticker[i]
            tmp_1 += sticker[i+1]
            
        if tmp_0 < tmp_1:
            answer = tmp_1
        else:
            answer = tmp_0
    # 홀수
    else:
        for j in range(len(sticker)):
            tmp = sticker[j]
            tmp_list = copy.deepcopy(sticker)
            
            if j == 0:
                del tmp_list[-1]
                del tmp_list[j: j+2]
            elif j == len(sticker)-1:
                del tmp_list[j-1:]
                del tmp_list[0]
            elif j == len(sticker)-2:
                del tmp_list[j-1:]
            else:
                del tmp_list[j-1: (j+2) % len(sticker)] # 인덱스 3일때 오류
            
#             print(tmp, tmp_list)
            
            tmp_0, tmp_1 = 0, 0
            for l in range(0,len(tmp_list),2):
                tmp_0 += tmp_list[l]
                tmp_1 += tmp_list[l+1]
            tmp_0 += tmp
            tmp_1 += tmp
            
            if answer < tmp_1:
                answer = tmp_1
            elif answer < tmp_0:
                answer = tmp_0
            
    return answer

 

📌다른사람의 문제풀이

- 결국 답은 DP

- 관련 설명은 하단 블로그 참조

velog

def solution(sticker):

    if len(sticker) == 1:
        return sticker[0]
    dp = [0 for _ in range(len(sticker))]  # use first sticker
    dp2 = [0 for _ in range(len(sticker))]  # unused first sticker

    dp[0] = sticker[0]
    dp[1] = sticker[0]

    dp2[0] = 0
    dp2[1] = sticker[1]
	
    # 첫번째 스티커를 사용했을 경우, 맨 끝 스티커 사용 못함
    for i in range(2, len(sticker) - 1):
        dp[i] = max(dp[i - 2] + sticker[i], dp[i - 1])

    value_1 = max(dp)

    for i in range(2, len(sticker)):
        dp2[i] = max(dp2[i - 2] + sticker[i], dp2[i - 1])
    value_2 = max(dp2)

    answer = max(value_1,value_2)
    return answer

 

📌리뷰

- 경우의 수가 많다고 판단될때는 DP 한 번 생각해보기