프로그래머스 - 도둑질

도둑질

설명

각 집들은 서로 인접한 집들과 방범장치가 연결되어 있기 때문에 인접한 두 집을 털면 경보가 울립니다.

각 집에 있는 돈이 담긴 배열 money가 주어질 때, 도둑이 훔칠 수 있는 돈의 최댓값을 return 하도록 solution 함수를 작성하세요.

제한사항
이 마을에 있는 집은 3개 이상 1,000,000개 이하입니다.
money 배열의 각 원소는 0 이상 1,000 이하인 정수입니다.

# n//2개 까지 털 수 있음
# 그치만 많이 턴다 -> 돈이 최대이다 보장x
# 한 집씩 옮겨가며 최대값 갱신? -> 전전집+지금집 vs 이전집
# 첫 집은 비교대상이 없음 -->>>>???? 일단 털자


def solution(money):
    answer = 0
    thief1 = [0]*len(money)
    thief2 = [0]*len(money)
    
    for i in range(len(money)-1): # 첫 집 털면 마지막 집 못털음
        thief1[i] = max(thief1[i - 1], thief1[i - 2] + money[i])
    print(thief1[-2]) # 절반은 실패함, 첫집이 문제인듯
    
    for i in range(1, len(money)): # 첫 집 안털면?
        thief2[i] = max(thief2[i - 1], thief2[i - 2] + money[i])
    print(thief2[-1])
    answer = max(thief1[-2], thief2[-1])
    return answer

• 우선 최대로 많이 털 수 있는 집의 개수는 절반까지
• 그치만 많이 턴다 -> 최대로 턴다는 아님
• 결국 하나씩 털어가며 이것도 계속 최대값 갱신하는 문제인듯
• 왜냐? 내가 이 집을 터는게 최대가 될지 말지는 딱 전전집까지만 영향을 주기 때문
• 전전집+현재집 vs 이전집 하나 이렇게 비교하는 구도인데, 첫집은 어떻게?
• 그래서 첫 집 터는걸로 코드를 짜봤더니 절반 정도만 해결이 되더라
• 두 가지 경우를 다 구해보고 더 큰 금액으로 return하였음