https://programmers.co.kr/learn/courses/30/lessons/42897
코딩테스트 연습 - 도둑질 | 프로그래머스
도둑이 어느 마을을 털 계획을 하고 있습니다. 이 마을의 모든 집들은 아래 그림과 같이 동그랗게 배치되어 있습니다. 각 집들은 서로 인접한 집들과 방범장치가 연결되어 있기 때문에 인접한 두 집을 털면 경보가 울립니다. 각 집에 있는 돈이 담긴 배열 money가 주어질 때, 도둑이 훔칠 수 있는 돈의 최댓값을 return 하도록 solution 함수를 작성하세요. 제한사항 이 마을에 있는 집은 3개 이상 1,000,000개 이하입니다. money 배열의 각
programmers.co.kr
직전에 풀었던 프로그래머스 문제 '스티커 붙이기'와 동일한 방법으로 풀 수 있는 문제.
table[i]를 'i번째 집까지 털었을 때 최댓값'이라고 정의하면
1) i-1번째 집을 이미 털었을 경우 -> i번째 집은 털지 못한다 = table[i-1]과 같은 값
2) i-1번째 집을 털지 않았을 경우 -> table[i-2] + money[i]
가 된다.
따라서 점화식은
table[i] = max(table[i-1], table[i-2] + money[i]) 가 된다.
여기서, 첫 번째 집을 털었는지 아닌지에 따라 마지막 집을 털 수 있는지 없는지가 달라지는데
만약 첫 번째 집을 털었을 경우 table[0] = money[0]이 되고, 맨 마지막 집은 털 수 없게 된다.
첫 번째 집을 털지 않은 경우 table[0] = 0, table[1] = money[1]이 된다. 맨 마지막 집은 최댓값 여부에 따라 털 수도, 아닐 수도 있다.
| def solution(money): | |
| table = [0 for _ in range(len(money))] | |
| # 첫 번째 집을 털 경우 | |
| table[0] = money[0] | |
| table[1] = table[0] | |
| for i in range(2, len(money) - 1): | |
| table[i] = max(table[i-1], table[i-2] + money[i]) | |
| value = max(table) | |
| # 첫 번째 집을 털지 않을 경우 | |
| table = [0 for _ in range(len(money))] | |
| table[1] = money[1] | |
| for i in range(2, len(money)): | |
| table[i] = max(table[i-1], table[i-2] + money[i]) | |
| return max(value, max(table)) |
'프로그래밍 > 코딩테스트 문제풀이' 카테고리의 다른 글
| [Python] 백준 15683. 감시 (0) | 2020.01.28 |
|---|---|
| [Python] 프로그래머스. 여행경로 (Level 3) (0) | 2020.01.24 |
| [Python] 프로그래머스. 스티커 모으기(2) (Level 4) (0) | 2020.01.18 |
| [Python] 프로그래머스. 땅따먹기 (Level 2) (0) | 2020.01.16 |
| [Python] 백준 2667. 단지번호붙이기 (0) | 2020.01.15 |