개미전사

문제 

식량창고가 있을 때 최소한 한칸이상 차이가 나야 약탈을 연속으로 가능하다.

 

 

유형 파악 및 구현

내가 나름 정한 규칙이 있다.

전의 값이 지금 구하고자하는 값에 영향을 주는 가? DP

2차원 그래프에서 특정조건에 맞춰 연결된 집합을 구하거나 거리를 구하는가? DFS/BFS

완전탐색이나 시뮬레이션 문제 유형인가? Implementation

아무 생각이 안나는가? Greedy

 

뭐 이 중에서 알고리즘이 섞여서 나오기도 하지만 기본적으로는 저런 조건이 있다면 해당 알고리즘을 생각해내는게 중요하다.

 

이 문제는 전에 구한값이 지금 구하는 값에 영향을 미친다.

식량 창고가 다음과 같다고 가정하자

[2, 1, 9, 10, 11, 8]

첫번째 인덱스까지만 존재한다고 가정하고 턴다면 최대값은 2이다. check[1] = 2

두번째 인덱스까지만 존재한다고 가정하고 턴다면 최대값은 2이다. check[2] = 1

세번째 인덱스까지만 존재한다고 가정하고 턴다면 최대값은 11이다. check[3] = 11

-> max(check[2], check[3-2]+1)

...

여섯번째 인덱스까지만 존재한다고 가정하고 턴다면 최대값은

-> max(check[6-1], check[6-2]+1)

 

 

코드

n = 8
food = [1, 3, 1, 5, 1, 1, 8, 10]
check = [0]*(n+1)
check[1] = food[0]
check[2] = max(check[1], food[1])

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