[ 파이썬(python) ] 이것이 코딩 테스트다 - 개미전사(DP)

📍 이것이 코딩 테스트다 DP - 개미 전사

유튜브 - 동빈나(27:48)

---

⚡️ 나의 풀이

3개월 전에 풀었던 문제이지만, 어떻게 풀었는지 기억이 잘 안 나서 다시 풀어봤다. 문제를 풀어보면 알겠지만 boj_2579 - 계단 오르기와 비슷한 유형이다.

 

입력 부분에서 맨 앞에 0을 주고 싶었는데 그렇게 되면 입력받는 부분이 까다로워질 수 있어 처음부터 입력값을 주었다. 그러면 출력으로 n-1을 줘야 된다는 점을 잊지 말자!

 

풀이 영상을 보면서 동빈 나가 DP를 써야 하는 경우를 알려주셨는데 기억해야 하는 내용이다.

1. 최적 부분: 특정 i번째까지 최적의 해를 구할 때 이전 값을 사용한다.

여기에서 제일 중요한 포인트는 개미가 식량창고를 털 때 두 가지의 케이스가 있다.
관점을 달리해서 뒤에서부터 살펴보자.

 

 

1. 제일 마지막 i번째 식량창고를 턴다: d [i] = food [i] + d [i-2]
2. 제일 마지막 i번째 식량창고를 털지 않는다: d [i] = d [i-1]

 

2번에서 d[i-3]을 넣지 않은 이유는 이미 table에 값을 저장해놨기 때문이다.

'''
4
1 3 1 5
'''

n = int(input())
food = list(map(int, input().split()))
d = [0] * 101

d[0] = food[0]
d[1] = max(food[0], food[1])

for i in range(2, n):    
    d[i] = max(food[i] + d[i - 2], d[i - 1])

print(d[n - 1])