My code
n = int(input())
k = list(map(int,input().split()))
d = [0] * 101
d[0] = k[0]
d[1] = max(k[0], k[1])
for i in range(2, n):
d[i] = max(d[i - 1], d[i - 2] + k[i])
print(d[n - 1])
Code Review
이번 문제는 일직선으로 이어진 식량 창고가 있을 때 얻을 수 있는 식량의 최댓값을 구하는 것 이었습니다. 단,
-서로 인접한 식량 창고는 약탈 할 수 없다 (한 칸 이상 떨어져야 함)
이 문제의 점화식을 세우기 위해서는 위의 조건을 꼭 고려해주어야 합니다.
-a(i) = max[a(i-1), a(i-2) + k(i)]
계속해서 구할 수 있는 식량의 최대값을 왼쪽부터 갱신해 나가므로 현재의 위치에서 -1, -2 번째 위치만 고려해주면 됩니다. 이때, i-1 번째의 식량은 약탈 할 수 없으므로 현재까지 구한 값으로 고려해주고, i-2 번째의 식량을 약탈 할 수 있으므로 식량의 값을 더해준 값으로 비교하여 max 값을 찾아 현재의 값을 갱신시켜줍니다. 이 과정을 반복하면 약탈 할 수 있는 식량의 최댓값을 구할 수 있습니다.
반복문을 2 부터 수행하는 이유는 0 과 1 번째 식량창고는 서로 인접한 식량창고만 존재하기 때문입니다. 따라서 0번째 식량 창고는 현재 식량의 개수로 갱신, 1번째 식량 창고는 0번째와 현재의 값을 비교했을 때 최댓값으로 갱신시켜 초기값으로 설정해줍니다.
댓글