💻 입력 조건

  • 첫째 줄에 식량창고의 개수 N이 주어진다. (3 <= N <= 100)
  • 둘째 줄에 공백으로 구분되어 각 식량창고에 저장된 식량의 개수 K가 주어진다. (0 <= K <= 1,000)

💻 출력 조건

  • 첫째 줄에 개미 전사가 얻을 수 있는 식량의 최댓값을 출력하시오.

💻 입력 예시

4
1 3 1 5

💻 출력 예시

8

📖 문제 해결
다이나믹 프로그래밍을 이용하여 왼쪽부터 오른쪽으로 한칸씩 이동해가면서 최댓값을 계산해나가는 방식으로 문제를 해결하였습니다.
메모를 하기 위한 리스트 d에는 각각의 위치에 있는 값을 포함하였을 때 만들어질 수 있는 최댓값을 기록하였습니다. (예를 들어, d[5]에는 k[5] 값을 반드시 포함하여 만들어질 수 있는 최댓값을 기록하였습니다.)
d[0], d[1], d[2]의 최댓값은 이미 한 가지로 정해져있는 값이기 때문에 미리 설정을 해두었고, idx>=3인 값들부터는 현재의 칸에 두 칸 전 혹은 세 칸 전의 최댓값과 더해보고 두 합 중 최댓 값인 것을 d[idx]에 입력하는 방식으로 최댓값을 계산해나갔습니다.
마지막으로 최종 최댓값은 맨 마지막 칸에 있는 값과 마지막 칸의 앞 쪽에 있는 값들 중 최대의 값을 구함으로써 찾았습니다.

# N을 입력받기
n = int(input())

# 식량창고에 저장된 식량의 개수들을 입력받기
k = list(map(int,input().split()))

# memo를 위한 리스트인 d 초기화
d = [0] * len(k)

# d[0], d[1], d[2] 값 설정
d[0] = k[0]
d[1] = k[1]
d[2] = k[2] + k[0]

# d의 idx의 값이 3 이상인 경우에는 비교를 하여 입력
for idx, item in enumerate(k):
    if idx >= 3:
        # 현재의 칸에 두 칸 전 혹은 세 칸 전의 최댓값과 더해보고
        # 두 합 중 최댓 값인 것을 d[idx]에 입력
        d[idx] = max((k[idx]+k[idx-2]),(k[idx]+k[idx-3]))

# 맨 마지막 칸에 있는 값과 마지막 칸의 앞쪽에 있는 값 중 더 큰 값을 출력
print(max(d[n-1],d[n-2]))
profile
AI를 공부하고 있는 학생입니다:)

0개의 댓글