[프로그래머스] 도둑질

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

코딩테스트 연습 - 도둑질

 

 

< 문제 설명 >

도둑이 집을 털려고 한다.

이때 서로 인접한 집은 방법장치가 연결되어있어 인접한 두 집은 털 수 없다.

money는 각 집을 털어 벌 수 있는 돈.

도둑이 최대로 훔칠 수 있는 돈을 리턴하면 된다.

 

 

< 문제 이해 >

일단 dp문제이기 때문에 식을 만들기 위한 고민을 했다.

인접한 집은 털 수 없기 때문에 전 집까지 훔칠 수 있는 최대 금액과

전전 집까지 훔칠 수 있는 최대 금액과 현재 집의 금액을 더한 값 중에 큰 값을 선택하면 된다.

 

 

< 시행 착오1 >

def solution(money):
    dp = [0] * (len(money)+1)	# 하나를 더 만들어준 이유는 i-2까지 필요해서
    dp[1] = money[0]		# 첫 집의 값을 넣는다.
    
    for i in range(2,len(money)+1):
        dp[i] = max(dp[i-1], dp[i-2]+money[i-1])	# dp
        
    print(dp)
    
    return max(dp)

처음에 단순히 식만 세워서 돌려봤다. 

위에 테스트의 예시는 통과했지만 [1, 3, 3, 1, 4] 의 경우 통과하지 못했다.

 

 

< 시행 착오2 >

def solution(money):
    dp = [0] * (len(money)+1)
    dp[1] = money[0]
    first = [False, True]	# 첫번째 값이 더해졌는지를 체크하는 것
    
    for i in range(2,len(money)+1):
        if dp[i-1] > dp[i-2]+money[i-1]:
            dp[i] = dp[i-1]
            first.append(first[i-1])	# dp[i-1]이 값이 된다면 first[i-1]
        else :
            dp[i] = dp[i-2]+money[i-1]
            first.append(first[i-2])	# dp[i-2]+money[i-1]이 된다면 first[i-2]
            
    print(dp)
    print(first)        
    
    if first[-1] == False : return dp[-1]	# 마지막 값에 첫번째 값이 더해지지 않았으면 dp[-1]리턴
    else : return max(dp[-2],dp[-1]-money[0])	# 더해졌다면 dp[-2]와 dp[-1]-money[0] 중에 큰거 리턴

위에 성공하지 못했던 예시는 통과했지만,

[2, 3, 2, 1, 4]의 경우는 통과하지 못했다.

3+4=7 이 가장 큰 값이 되는데 dp[i-1], dp[i-2]의 값으로 충분하지 않았다,,,,

 

 

< 문제 풀이 >

def solution(money):

    return max(calc(money[1:]),calc(money[:-1]))

def calc(money):
    dp = [0] * (len(money)+1)
    dp[1] = money[0]

    for i in range(2,len(money)+1):
        dp[i] = max(dp[i-1], dp[i-2]+money[i-1])

    return max(dp)

<시행착오1> 코드를 통해서 집이 둥글게 연결되어있지 않고 1자로 연결되어 있을 때는 문제없이 풀 수 있었다.

그래서 문제를 두개로 나눠서 생각해보기로 했다.

왜냐하면 첫번째 집과 마지막 집은 동시에 털 수가 없기 때문에

어차피 두 집 중 하나는 못 턴다.(물론 둘 다 못 털 수도 있음)

그래서 [2, 3, 2, 1, 4] 일 경우 [2, 3, 2, 1]과 [3, 2, 1, 4]로 나누어서 생각해보기로 했다.

 

<시행착오1> 코드를 함수로 만들어서 money[1:]과 money[:-1]을 넣고 돌린 뒤

둘 중에 큰 값을 리턴했다.

 

성공,,!@!@!!!@!!