💥이코테 실전문제 뽀개기💥

💻 8-2 개미 전사

난이도🖤🖤🤍 | 풀이시간 30분 | 제한시간 1초 | 메모리제한 128MB

---

📌2021/02/01 작성 코드

# 개미 전사
n = int(input())
rooms = [0] + list(map(int, input().split()))
dptable = [0]*(n+1)

for i in range(1, n+1):
    if i == 1:
        dptable[i] = rooms[i]
        continue
    if i == 2:
        dptable[i] = max(dptable[1], rooms[2])
        continue

    foods = []
    if 0 < i-2:
        foods.append(dptable[i-2] + rooms[i])
    if 0 < i-1:
        foods.append(dptable[i-1])
    dptable[i] = max(foods)

print(dptable[n])

---

💭 아이디어

• 솔루션이 쉽게 떠오르지 않아서 해설을 먼저 참고하고 혼자 코드를 짰다.

• 혼자 정리해 본 아이디어는 이렇다.
  
  ❗😨 수정! 그림에 나타내는 것을 깜빡했는데,
  CASE1의 경우 식량 = (i-1)까지 약탈한 식량이 맞는데
  CASE2의 경우에는 식량 = (i-2)까지 약탈한 식량 + i번째 식량창고에 있는 식량
  이 된다.
  
  이때, (i-3), (i-4)...에 대해서 탐색해보지 않아도 되는 이유는 이전의 과정들도 모두 CASE1 vs. CASE2를 비교하여 가장 좋은 경우를 값으로 취하고 있기 때문이다.
  ✨큰 문제를 작은 문제로 나눌 수 있으며, 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다✨

---

🤓 문제 해설

왼쪽부터 차례대로 식량창고를 턴다고 가정하면 어렵지 않게 점화식을 세울 수 있다. 왼쪽부터 차례대로 식량창고를 털지 안털지 결정하는 겨웅와 특정한 i번째 식량창고에 대해서 털지 안털지의 여부를 결정할 때, 단 2가지 경우에 대해서만 확인하면 된다.

1. (i-1)번째 식량창고를 털기로 결정한 경우 현재의 식량창고를 털 수 없다.
2. (i-2)번째 식량창고를 털기로 결정한 경우 현재의 식량창고를 털 수 있다.

따라서 1, 2 중 더 많은 식량을 털 수 있는 경우를 선택하면 된다.

여기서 알아둘 점은, 왼쪽부터 (i-3)번째 이하의 식량창고에 대해서는 고려할 필요가 없다. 왜냐하면 한 칸 이상 떨어진 식량창고는 항상 털 수 있기 때문이다. 따라서 i번째 식량창고에 있는 식량의 양이 ki라고 했을 때 점화식은 다음과 같다.

ai=max(ai-1, ai-2+ki)

---

🤓 답안 예시

# 정수 N을 입력 받기
n = int(input())
# 모든 식량 정보 입력 받기
array = list(map(int, input().split()))

# 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [0] * 100

# 다이나믹 프로그래밍(Dynamic Programming) 진행 (보텀업)
d[0] = array[0]
d[1] = max(array[0], array[1]) 
for i in range(2, n):
    d[i] = max(d[i - 1], d[i - 2] + array[i])

# 계산된 결과 출력
print(d[n - 1])

---

🤔 리뷰

• DP로 이런 것도 해결할 수 있구나.
• DP 조건을 외우고 있다가 적용할 수 있는 것들에 최대한 적용해 보는 게 좋겠다.
• 풀이 방법을 떠올리지 못했는데, 이런 문제는 이렇게 풀 수 있다는 것을 몰라서 그랬다. 앞으로 비슷한 문제가 나오면 해결할 수 있을 것이다.