[다이나믹 프로그래밍] ▲ 문제2 - 개미 전사(220p)

[이코테] 문제2 - 개미 전사(220p)

(한줄평) 다이나믹 프로그래밍을 풀어야함을 알고 점화식을 도출해낼 수있는 능력을 요구하는 문제로 복습이 꼭 필요한 문제!

---

---

(풀이1) 내 풍이

풀이 시간: 30분 이내

1) 문제 해결 아이디어

처음에 내가 생각해냈던 아이디어는 창고 최대 개수인 100개 크기로 생성한 리스트(d)에 해당 번호의 창고를 털었을 때 얻을 수 있는 식량의 최댓값을 기록하는 것이었다.

사실 예제로는 답이 맞게 나오는데 정확히 맞는 코드인지는 모르겠다....

 

2) 소스코드

n = int(input())  # 창고 개수
graph = list(map(int, input().split()))  # n개의 식량 개수

d = [0] * 100
d[0], d[1] = graph[0], graph[1]

# i번째 창고 털기
for i in range(2, n):
  d[i] = max(d[: i - 1]) + graph[i]

print(max(d))

 

(풀이2) 책 풀이

풀이 시간: 

1) 문제 해결 아이디어

기본 아이디어는 내 풀이와 똑같다. 다만 점화식을 세운 부분에 차이가 조금 있다.

 

<점화식>

이 문제는 인접한 창고는 털 수 없다는 점에서 경우의 수를 어떻게 나눌 수 있는지 떠올리는 것이 핵심이다!

그러므로 i번째 창고를 털 수 있을지 없을지는 i - 1번째를 털었을 경우와 i - 2번째 창고를 털었을 경우(i - 1 번째를 털지 않았을 경우) 2가지 경우로 나누어 생각해 볼 수 있다. 그 2가지 경우 중 최댓값을 i번째 식량창고까지 얻을 수 있는 최대 식량 값으로 설정하면된다.

 

1. i - 1 번째를 털었을 경우,

i번째는 인접했으므로 털 수 없게되어 그대로 i - 1번째 값이 될 것이고

2. i - 2 번째를 털었을 경우,

i번째는 인접하지않았으므로 털 수 있게 되므로 i - 2번째 값에 현재 i번째 창고의 식량 개수를 더한 값이 된다.

 

2) 소스코드

n = int(input())  # 창고 개수
graph = list(map(int, input().split()))  # n개의 식량 개수

d = [0] * 100
d[0] = graph[0]
d[1] = max(graph[0], graph[1])  # 둘 중 최댓값
for i in range(2, n):
  d[i] = max(d[i - 1], d[i - 2] + graph[i])

print(d[n - 1])