Lv4. 도둑질

# 문제 설명

도둑이 어느 마을을 털 계획을 하고 있습니다. 이 마을의 모든 집들은 아래 그림과 같이 동그랗게 배치되어 있습니다.

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

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

# 제한 사항

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

# 입출력 예

문제 해결 시 고려사항

• 집들의 구성은 환형임에 주의하자

본 문제는 인접한 집들을 도둑질하지 않고 최대의 money를 도둑질 했을때의 총액을 반환하는 문제이다. 집들은 환형으로 구성되어 있기 때문에, 아래와 같이 두 가지 경우로 나뉜다.

1. 첫 번째 집을 도둑질 할 경우에는, 마지막 집을 도둑질하지 못한다.
2. 첫 번째 집을 도둑질 하지 않을 경우에는, 마지막 집을 도둑질 할 수 있다.

위와 같이 경우를 두 가지로 나누어 Dynamic Programming하면 문제를 해결할 수 있다.

 # 마을은 환형이기 때문에 처음 집의 포함 여부를 구분하여 처리해주어야 함
 # 첫 집을 포함하여 도둑질 하는 경우를 위함
 dpfirst = [money[0], money[0], money[0] + money[2]]
 # 첫 집을 건너뛰고 도둑질을 하는 경우를 위함
 dpsecond = [0, money[1], max(money[1],money[2])]

필자는 위와 같이 dp를 dpfirst와 dpsecond로 나누어 계산해 나갔다. 집은 3개 이상이라고 문제에서 주어졌기 때문에 3개의 집까지 리스트를 초기화 시켰다. 이 초기화 단계에서 위에서 말한 경우를 고려하여 초기화하였다.

이 후 집이 4개 이상인 경우를 위해 아래와 같은 반복문을 구성하였다.

 # 4 번째 집부터 아래와 같은 규칙에 의해 반복
 for i in range(3, len(money)):
 # 해당 집 2 번째 집까지의 최대값과 3 번째 집까지의 최대값 중 최대에 해당 집의 money 추가
 dpfirst.append(max(dpfirst[i-2], dpfirst[i-3])+money[i])
 dpsecond.append(max(dpsecond[i-2], dpsecond[i-3])+money[i])  

인접한 집을 도둑질 할 수 없기 때문에 각각 해당 차례의 집보다 2번째, 3번째 집까지의 최대값에 해당 차례의 집의 money를 더해준 값을 append 해주어 나간다. 이 후, 아래와 같이 값을 반환하여 주면 된다.

 # dpfirst: 첫 번째 집을 포함했기 때문에 마지막에서 2번째, 3번재 집 중 최대값 비교
 # dpsecond : 첫 번재 집을 포함하지 않았기 때문에 마지막에서 1번째, 2번째 집 중 최대값 비교
 # 위 4가지 값 중 최대값을 반환
 return max(dpfirst[-2], dpfirst[-3], dpsecond[-1], dpsecond[-2]) 

전체 코드

def solution(money):
    # 마을은 환형이기 때문에 처음 집의 포함 여부를 구분하여 처리해주어야 함
    # 첫 집을 포함하여 도둑질 하는 경우를 위함
    dpfirst = [money[0], money[0], money[0] + money[2]]
    # 첫 집을 건너뛰고 도둑질을 하는 경우를 위함
    dpsecond = [0, money[1], max(money[1],money[2])]
    
    # 4 번째 집부터 아래와 같은 규칙에 의해 반복
    for i in range(3, len(money)):
        # 해당 집 2 번째 집까지의 최대값과 3 번째 집까지의 최대값 중 최대에 해당 집의 money 추가
        dpfirst.append(max(dpfirst[i-2], dpfirst[i-3])+money[i])
        dpsecond.append(max(dpsecond[i-2], dpsecond[i-3])+money[i])    
    # dpfirst: 첫 번째 집을 포함했기 때문에 마지막에서 2번째, 3번재 집 중 최대값 비교
    # dpsecond : 첫 번재 집을 포함하지 않았기 때문에 마지막에서 1번째, 2번째 집 중 최대값 비교
    # 위 4가지 값 중 최대값을 반환
    return max(dpfirst[-2], dpfirst[-3], dpsecond[-1], dpsecond[-2])