프로그래머스 12971] 스티커모으기(2) - 파이썬

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

def solution(sticker):
    if len(sticker) <= 3:
        return max(sticker)

    answer = 0
    # 첫번째 스티커
    dp1 = [0 for _ in range(len(sticker))]
    dp1[0], dp1[1] = sticker[0], sticker[0]

    # 첫번째 스티커 아닌 경우
    dp2 = [0 for _ in range(len(sticker))]
    dp2[0], dp2[1] = 0, sticker[1]

    print(dp1)
    # [14, 14, 0, 0, 0, 0, 0, 0]

    print(dp2)
    # [0, 6, 0, 0, 0, 0, 0, 0]

    for i in range(2, len(sticker)):
        if i == len(sticker) - 1:
            dp2[i] = max(dp2[i - 1], sticker[i] + dp2[i - 2])
        else:
            dp1[i] = max(dp1[i - 1], sticker[i] + dp1[i - 2])
            dp2[i] = max(dp2[i - 1], sticker[i] + dp2[i - 2])
        print(i, dp1, dp2)
        # 2 [14, 14, 19, 0, 0, 0, 0, 0]       [0, 6, 6, 0, 0, 0, 0, 0]
        # 3 [14, 14, 19, 25, 0, 0, 0, 0]      [0, 6, 6, 17, 0, 0, 0, 0]
        # 4 [14, 14, 19, 25, 25, 0, 0, 0]     [0, 6, 6, 17, 17, 0, 0, 0]
        # 5 [14, 14, 19, 25, 25, 34, 0, 0]    [0, 6, 6, 17, 17, 26, 0, 0]
        # 6 [14, 14, 19, 25, 25, 34, 34, 0]   [0, 6, 6, 17, 17, 26, 26, 0]
        # 7 [14, 14, 19, 25, 25, 34, 34, 0]   [0, 6, 6, 17, 17, 26, 26, 36]

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

print(solution([14, 6, 5, 11, 3, 9, 2, 10]))
# 36

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

def solution(stickers_list):
    num_of_stickers = len(stickers_list)
    if num_of_stickers == 1 : return stickers_list[0]
    stickers_list.insert(0, 0)

    # no take off the first sticker
    # score = ( take off sticker value, non-take off sticker value)
    max_score_list = [None, (0, 0)]
    for idx in range(2, num_of_stickers + 1):
        non_taken_off_value = max( max_score_list[idx-1][0], max_score_list[idx-1][1])
        do_taken_off_value = max_score_list[idx-1][1] + stickers_list[idx]
        max_score_list.append( (do_taken_off_value, non_taken_off_value))
    no_taken_off_first_maximum_value = max( max_score_list[num_of_stickers][0], max_score_list[num_of_stickers][1])

    # take off the first sticker
    max_score_list = [None, ( stickers_list[1], 0)]
    for idx in range(2, num_of_stickers):
        non_taken_off_value = max(max_score_list[idx - 1][0], max_score_list[idx - 1][1])
        do_taken_off_value = max_score_list[idx - 1][1] + stickers_list[idx]
        max_score_list.append((do_taken_off_value, non_taken_off_value))
    taken_off_first_maximum_value = max(max_score_list[num_of_stickers-1][0], max_score_list[num_of_stickers-1][1])

    answer = max( no_taken_off_first_maximum_value, taken_off_first_maximum_value)

    return answer