반응형
https://school.programmers.co.kr/learn/courses/30/lessons/42897
문제 해결 아이디어
- 어차피 돈은 양수이기에 두칸씩 띄어서 선택하면 장땡이다
- 첫번째 집과 마지막집은 붙어있기에 동시에 선택을 못한다
- 둘중하나 선택을 안하면 직선처럼 문제를 생각할 수 있다
- 두케이스중 큰값을 골라준다
def solution(money):
answer = 0
# 마지막집을 선택하지 않은경우
dp = [0] * len(money)
dp[0] = money[0]
dp[1] = max(money[0], money[1])
for i in range(2, len(money) - 1):
dp[i] = max(dp[i-2] + money[i], dp[i-1])
answer = max(answer, max(dp))
#첫번째 집을 선택하지 않은 경우
dp = [0] * len(money)
dp[0] = 0
dp[1] = money[1]
for i in range(2, len(money)):
dp[i] = max(dp[i-2] + money[i], dp[i-1])
answer = max(answer, max(dp))
return answer
반응형
'Python > 알고리즘문제' 카테고리의 다른 글
[프로그래머스][완전탐색] 카펫 (0) | 2021.04.15 |
---|---|
[프로그래머스][완전탐색] 소수 찾기 (0) | 2021.04.15 |
[프로그래머스][동적계획법] 등굣길 (0) | 2021.04.13 |
[프로그래머스][동적계획법] 정수 삼각형 (0) | 2021.04.13 |
[프로그래머스][탐욕법] 큰 수 만들기 (0) | 2021.04.02 |
댓글