[C++]백준 13002번: Happy Cow

문제 출처

풀이

문제가 생각보다 간단하다. n일째 날에는 n-1일째 날의 정보를 바탕으로 왼쪽 혹은 오른쪽에서 여물을 빼와서 계산하면 되는 문제이다. n일에 n-1일의 정보가 필요하므로 DP문제이다.
여물의 총 길이가 N이라고 하자. 그럼 여물 배열의 0부터 N-1까지 여물이 존재하는 것이다. 첫째 날이면 0혹은 N-1번째 여물을 소에게 주면된다. 그럼 남은 여물은 N-1개가 된다. i번 째 날이면 남은 여물은 N-i가 된다. 이이것을 구현하기 위해 나는 l이라는 남은 여물의 개수를 계산하는 변수를 두었고 l을 하루하루 지날 때마다 1씩 감소시켰다. 그 다음에 i라는 변수를 두었고 이 i는 여물의 시작지점을 나타내는 변수이다. i+l은 여물의 끝지점을 나타내게 된다. 여물의 개수가 N이기 때문에 i+l은 N-1을 넘어서는 안된다. 코드는 다음과 같다.

#include<iostream>
#include<vector>
#include<queue>

using namespace std;

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int N;
	cin >> N;
	vector<vector<int>> dp(N, vector<int>(N,0));
	vector<int> happy(N);
	for ( int i = 0; i < N ; i++ ) {
		cin >> happy[i];
	}
	int left, right;
	int idx = 0;
	for ( int l = N-2; l >= 0; l-- ) {
    	//dp[i][i+l]을 계산할 때 왼쪽, 오른쪽 여물을 먹는 경우를 비교해
        //더 큰 값을 dp[i][i+1]로 결정한다.
    	//경과한 일수
		idx++;
		for ( int i = 0; i + l < N; i++ ) {
			left = 0;
			right = 0;
			if ( i - 1 >= 0 ) {
            	//왼쪽 여물을 먹는 경우
				left = dp[i - 1][i + l] + happy[i - 1] * idx;
			}
			if ( i + l + 1 < N ) {
            	//오른쪽 여물을 먹는 경우
				right = dp[i][i + l + 1] + happy[i + l + 1] * idx;
			}

			dp[i][i + l] = max(left, right);
		}
	}
	int res = -1;
	idx++;
    
	for ( int i = 0; i < N; i++ ) {
		res = max(res, dp[i][i] + happy[i] * idx);		
	}

	cout << res << endl;
	return 0;
}