Treat/권영기

결과

run-id user id 프로그램 명 결과 언어 경과 시간(초) 코드 사이즈(byte) 제출 시간 1373722 zeropage treat accept C++ 0.17 484 2014-07-17 06:08

설명

• 쿠키는 항상 가장 왼쪽이나 오른쪽부터 팔 수 있다. 즉 중간부터 팔 수 없음. 우리가 쿠키가 N개 있다고 할 때, j번째 쿠키를 판다면, 그것은 (1 ~ j-1)번째 쿠키가 팔려있는 상황이거나, (j + 1 ~ N)번째 쿠키가 팔려있는 상황이어야 함.
• 우리가 쿠키를 지금 i개 판 상황일 때, 왼쪽에서 j개를 팔았다면, 오른쪽에서는 i - j개 팔려있는 상황임. 즉 전체 판 쿠키의 양과, 왼쪽부터 판 쿠키의 양을 알면 오른쪽부터 판 쿠키의 양은 정해짐. -> 고려해야 할 변수는 1. 지금까지 몇 개의 쿠키를 팔았는가, 2. 쿠키를 팔았다면, 왼쪽에서 몇 개 팔았는가. 이다.
• 이를 고려하여 점화식을 구하면,

• d(i, j) : 쿠키를 i개 팔았을 때, 왼쪽에서 다음 팔 수 있는 쿠키가 j번째 쿠키인 경우 얻을 수 있는 최대 돈의 양.

for(int i = 1; i<=n; i++){
	for(int j = 0; j<i; j++){
		d[i][j] = max(d[i][j], d[i-1][j] + (i * cookie[n - i + j]));
		d[i][j+1] = max(d[i][j+1], d[i-1][j] + (i * cookie[j]));
	}
}

소스

#include<iostream>
using namespace std;
const int size = 2020;
int n;
int d[size][size], cookie[size];
int main(void)
{
	cin>>n;
	for(int i = 0; i<n; i++){
		cin>>cookie[i];
	}
	for(int i = 1; i<=n; i++){
		for(int j = 0; j<i; j++){
			d[i][j] = max(d[i][j], d[i-1][j] + (i * cookie[n - i + j]));
			d[i][j+1] = max(d[i][j+1], d[i-1][j] + (i * cookie[j]));
		}
	}
	int ans = 0;
	for(int i = 0; i<n; i++){
		ans = max(ans, d[n][i]);
	}
	cout<<ans;

	return 0;
}