개미 전사

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int dp[101][2];
int food[101];

int main() {
  freopen("input.txt","r",stdin);
  int n;
  cin>>n;

  for(int i=1;i<=n;i++)
    cin>>food[i];

  dp[1][0]=0;
  dp[1][1]=food[1];
  dp[2][0]=food[1];
  dp[2][1]=food[2];
  for(int i=3;i<=n;i++){
    dp[i][1]=max(dp[n-2][1],dp[n-2][0])+food[i];
    dp[i][0]=max(dp[n-1][1],dp[n-1][0]);
  }

  cout<<dp[n][0]<<" "<<dp[n][1];
}

나의 코드이다. 풀이과정은 다음과 같다.

총 N개의 음식이 있고, 마지막 창고를 털었을때와 털지 않았을때로 구분해서 점화식을 세웠다. dp배열은 2차원으로 구성했으며, 첫번째 인덱스는 창고의 총 개수, 두번째 인덱스는 그 창고를 털었다면 1, 털지 않았다면 0을 넣었다.

1. 마지막 창고를 털었을때

마지막 창고를 털었으면 마지막에서 두번째 창고는 털 수 없다. 그래서 N-2 번째 창고부터 털 수 있다. 따라서 점화식으로 

dp[N][1] = max (dp[N-2][0],dp[N-2][1]) + food[N]

이 된다. 마지막 창고를 털었으니까 food[N] 을 더해주어야 한다.

 

2. 마지막 창고를 털지 않았을때

이렇게 되면 N-1 번째 창고부터 털 수 있게된다. 따라서 점화식으로 써보면 

dp[N][0] = max(dp[N-1][0],dp[N-1][1]) 

이 된다. 이때 마지막 창고는 털지 않았으니 food[N] 은 더해주지 않아야 한다.

 

이렇게 bottom-up 으로 계산한 후에 dp[N][0] 과 dp[N][1] 중에서 큰 값을 출력하면 된다. 전자가 선택되었다면 N번째 창고는 털지 않은 것이고, 후자가 선택 되었다면 마지막 창고가 털린것이다.

 

책의 정답 코드는 다음과 같다.

#include <bits/stdc++.h>

using namespace std;

// 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
int d[100];
int n;
vector<int> arr;

int main(void) {
    // 정수 N을 입력받기
    cin >> n;
    // 모든 식량 정보 입력받기
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        arr.push_back(x);
    }

    // 다이나믹 프로그래밍(Dynamic Programming) 진행(보텀업)
    d[0] = arr[0];
    d[1] = max(arr[0], arr[1]);
    for (int i = 2; i < n; i++) {
        d[i] = max(d[i - 1], d[i - 2] + arr[i]);
    }

    // 계산된 결과 출력
    cout << d[n - 1] << '\n';
}

여기서는 일차원 배열을 사용했다. 나와는 조금 다르게 맨 처음 부터 차례대로 창고를 턴다고 가정하고 식을 세웠다. 이렇게 되면 특정한 i번째 창고를 털것인가 털지 않을 것인가 이 두개로 나뉘게 된다.

 

1. i-1번째 창고를 털었을때

i 번째 창고는 털 수 없다

이곳을 털면!

현재 창고(털수없음)

2. i-2번째 창고를 털었을때

i-1번째 창고는 털 수 없고 i번째 창고는 털 수 있다.

이곳을 털면!

현재 창고(털수있음)

위의 두가지 방식 중 큰 값을 택하여 결정하면 된다.