Py) 프로그래머스 42897 도둑질

 

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

코딩테스트 연습 - 도둑질

이렇게 실패만 주르륵 뜨는 거 처음 본다. 사정없이 빨간 글자가 파바바바ㅏ박

니 코드는 볼 것도 없다ㅋ 느낌이었다. 

알겠어어아악그만해

* 틀린 코드

def solution(money):
    answer = 0
    steal = []

    for house, amount in enumerate(money):
        steal.append([house,amount])

    for j in range(0, len(money)-1, 2): # 0포함
         answer += steal[j][1]
    tmp = 0
    for j in range(1, len(money), 2): # 0 미포함
        tmp += steal[j][1]
    answer = tmp if answer < tmp else answer

    return answer

아무래도 문제 자체를 잘못 생각한 것 같다.

 

* 정답 코드

def solution(money):

    dp1 = [0] * len(money)
    dp2 = [0] * len(money)

    dp1[0] = money[0]
    for i in range(1, len(money)-1):    # 0을 포함
        dp1[i] = max(dp1[i-2]+money[i], dp1[i-1])

    dp2[0] = 0
    for j in range(1, len(money)):
        dp2[j] = max(dp2[j-2]+money[j], dp2[j-1])

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

단순히 0 포함 미포함만 생각하면서 홀수 짝수 더한 게 잘못된 생각이었다.

현재 돈을 훔치는 게 이익인지, 이전 돈을 훔치는게 이익인지 고려해야 했다.

 

dp가 약한 것 같다.

다른 것들보다 dp 풀면 음 ㅇㅇ 낯선 느낌? 집 가면.. dp를 좀 파자..