[프로그래머스] 도둑질 / 파이썬(python)

# 문제 링크

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

코딩테스트 연습 - 도둑질

# Soultion

시간초과문제가 발생하므로 DP를 이용하여 문제해결

############시간초과#############
def solution(money):
    answer = 0
    a = money[:len(money)-1]
    for i in range(2,len(a)):
        a[i] += max(a[:i-1])
    b = money[1:]
    for i in range(2,len(b)):
        b[i] += max(b[:i-1])
 
    return max(a+b)
 
#################################
def solution(money):
    answer = 0
    a = money[:len(money)-1]
    a[1] = max(a[0],a[1])
    for i in range(2,len(a)):
        a[i] = max(a[i-1],a[i-2]+a[i])
    b = money
    b[0]=0
    b[1] = max(b[0],b[1])
    for i in range(2,len(b)):
        b[i] = max(b[i-1],b[i-2]+b[i])
    return max(a+b)

 

16. 마지막 집은 무조건 들리지 않는다고 가정하고 문제풀기

17. 2번째 인덱스에 들은 값은 자신앞의 수와비교와 큰 수 저장

18. 3번째 인덱스부터 비교

19. (한칸앞의 최대값과, 두칸앞 최대값+현재나의값)을 비교하여 더 큰 값을 현재 값에 저장

20. 위와 동일하지만, 첫번째 집은 들리지 않는다고 가정하고 문제풀기