코딩테스트/프로그래머스
[프로그래머스] 도둑질 / 파이썬(python)
Jiwon_C
2021. 5. 28. 23:18
# 문제 링크
https://programmers.co.kr/learn/courses/30/lessons/42897
코딩테스트 연습 - 도둑질
도둑이 어느 마을을 털 계획을 하고 있습니다. 이 마을의 모든 집들은 아래 그림과 같이 동그랗게 배치되어 있습니다. 각 집들은 서로 인접한 집들과 방범장치가 연결되어 있기 때문에 인접한
programmers.co.kr
# Soultion
시간초과문제가 발생하므로 DP를 이용하여 문제해결
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
############시간초과#############
def solution(money):
answer = 0
a = money[:len(money)-1]
for i in range(2,len(a)):
a[i] += max(a[:i-1])
b = money[1:]
for i in range(2,len(b)):
b[i] += max(b[:i-1])
return max(a+b)
#################################
def solution(money):
answer = 0
a = money[:len(money)-1]
a[1] = max(a[0],a[1])
for i in range(2,len(a)):
a[i] = max(a[i-1],a[i-2]+a[i])
b = money
b[0]=0
b[1] = max(b[0],b[1])
for i in range(2,len(b)):
b[i] = max(b[i-1],b[i-2]+b[i])
return max(a+b)
|
cs |
16. 마지막 집은 무조건 들리지 않는다고 가정하고 문제풀기
17. 2번째 인덱스에 들은 값은 자신앞의 수와비교와 큰 수 저장
18. 3번째 인덱스부터 비교
19. (한칸앞의 최대값과, 두칸앞 최대값+현재나의값)을 비교하여 더 큰 값을 현재 값에 저장
20. 위와 동일하지만, 첫번째 집은 들리지 않는다고 가정하고 문제풀기