코딩

[프로그래머스] 도둑질, 스티커모으기 .py 본문

코딩테스트

[프로그래머스] 도둑질, 스티커모으기 .py

ssooyn_n 2021. 3. 3. 21:05

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

 

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

N개의 스티커가 원형으로 연결되어 있습니다. 다음 그림은 N = 8인 경우의 예시입니다. 원형으로 연결된 스티커에서 몇 장의 스티커를 뜯어내어 뜯어낸 스티커에 적힌 숫자의 합이 최대가 되도록

programmers.co.kr

programmers.co.kr/learn/courses/30/lessons/42897

 

코딩테스트 연습 - 도둑질

도둑이 어느 마을을 털 계획을 하고 있습니다. 이 마을의 모든 집들은 아래 그림과 같이 동그랗게 배치되어 있습니다. 각 집들은 서로 인접한 집들과 방범장치가 연결되어 있기 때문에 인접한

programmers.co.kr

 

 

def solution(sticker):
    n = len(sticker)
    if n <= 2:
        return max(sticker)
    
    dp1 = [sticker[0], sticker[0]]
    dp2 = [0, sticker[1]]
    
    for i in range(2, n):
        dp2.append(max(dp2[i-2] + sticker[i], dp2[i-1]))
        if i < n - 1:
            dp1.append(max(dp1[i-2] + sticker[i], dp1[i-1]))
    
    return max(dp1[-1], dp2[-1])

 

현재 index list[i]list[i-2]까지 더한 값  list[i-1]까지 더한 값을 비교하여 그 중 큰 값을 dp[i]에 저장.

dp[i] = max(dp[i-2] + list[i], dp[i-1]) 

이때, 리스트는 원형이므로 첫번째 index를 취하는 경우와 취하지않는 경우를 나누어준다.

 

1. 첫번째 index부터 시작할 경우 # 인접한 두번째 index는 계산할 수 없으므로 dp1[1]의 최댓값은 dp[0]이 된다.

dp1 = [list[0], list[0]]

 

2. 두번째부터 시작할 경우 # 첫번째는 계산하지 않으므로 dp[0]의 최댓값은 0 dp[1]의 최댓값은 list[1]이 된다.

dp2 = [0, list[1]]

Comments