Treat/권영기 - Revision history

Maintenance script: Repair batch-0008 pages from live compare

2026-03-27T01:40:37Z

Repair batch-0008 pages from live compare

← Older revision		Revision as of 01:40, 27 March 2026
Line 14:		Line 14:
	for(int i = 1; i<=n; i++){		for(int i = 1; i<=n; i++){
	for(int j = 0; j<i; j++){		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] = 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]));		d[i][j+1] = max(d[i][j+1], d[i-1][j] + (i * cookie[j]));
	}		}
	}		}
Line 25:		Line 25:
	const int size = 2020;		const int size = 2020;
	int n;		int n;
	int d[size][size], cookie[size];		int d[size][size], cookie[size];
	int main(void)		int main(void)
	{		{
	cin>>n;		cin>>n;
	for(int i = 0; i<n; i++){		for(int i = 0; i<n; i++){
	cin>>cookie[i];		cin>>cookie[i];
	}		}
	for(int i = 1; i<=n; i++){		for(int i = 1; i<=n; i++){
	for(int j = 0; j<i; j++){		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] = 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]));		d[i][j+1] = max(d[i][j+1], d[i-1][j] + (i * cookie[j]));
	}		}
	}		}
	int ans = 0;		int ans = 0;
	for(int i = 0; i<n; i++){		for(int i = 0; i<n; i++){
	ans = max(ans, d[n][i]);		ans = max(ans, d[n][i]);
	}		}
	cout<<ans;		cout<<ans;
Line 46:		Line 46:
	return 0;		return 0;
	}		}

imported>trailblaze at 21:22, 16 July 2014

2014-07-16T21:22:21Z

← Older revision		Revision as of 21:22, 16 July 2014
Line 1:		Line 1:
			== 결과 ==
			run-id user id 프로그램 명 결과 언어 경과 시간(초) 코드 사이즈(byte) 제출 시간
			1373722 zeropage treat accept C++ 0.17 484 2014-07-17 06:08


	== 설명 ==		== 설명 ==

imported>trailblaze at 21:20, 16 July 2014

2014-07-16T21:20:51Z

← Older revision		Revision as of 21:20, 16 July 2014
Line 5:		Line 5:
	* 이를 고려하여 점화식을 구하면,		* 이를 고려하여 점화식을 구하면,

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

	for(int i = 1; i<=n; i++){		for(int i = 1; i<=n; i++){

imported>trailblaze at 21:20, 16 July 2014

2014-07-16T21:20:29Z

New page

== 설명 ==

* 쿠키는 항상 가장 왼쪽이나 오른쪽부터 팔 수 있다. 즉 중간부터 팔 수 없음. 우리가 쿠키가 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;
}