블로그는 귀차니즘

문제링크 : http://icpcres.ecs.baylor.edu/onlinejudge/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=44
의 견 : Dynamic Programming을 배웠고, 사용한다면 쉬운 문제, 하지만 단순히 for 루프를 이용하여 6중 for 루프를 사용한다면 time exceed를 면할 수 없을 것입니다.
DP 방법은 배열을 사용할 때 [ 시작 x 인덱스 ][ 시작 y 인덱스 ][ 끝 x 인덱스 ][ 끝 y 인덱스 ]로 의미를 부여하여 대상 값들을 계산 후 업데이트하고 재사용합니다.
소스
108.cpp (Language : cpp)
1. #include <iostream>
3. using namespace std;
5. short Matrix[ 101 ][ 101 ][ 101 ][ 101 ] = { 0, };
7. int main( int argc, char **argv )
8. {
9. int MaxSum = -999999;
10. int size;
12. cin >> size;
14. for( int i = 1; i <= size; i++ ) {
15. for( int j = 1; j <= size; j++ ) {
16. cin >> Matrix[ i ][ j ][ i ][ j ];
17. }
18. }
20. for( int StartI = 1; StartI <= size; StartI++ ) {
21. for( int StartJ = 1; StartJ <= size; StartJ++ ) {
23. for( int EndI = StartI; EndI <= size; EndI++ ) {
24. for( int EndJ = StartJ; EndJ <= size; EndJ++ ) {
26. short RectangleSum = Matrix[ StartI ][ StartJ ][ EndI ][ EndJ - 1 ];
27. short LineSum = Matrix[ StartI ][ EndJ ][ EndI - 1 ][ EndJ ];
29. short NewLineSum = LineSum + Matrix[ EndI ][ EndJ ][ EndI ][ EndJ ];
30. Matrix[ StartI ][ EndJ ][ EndI ][ EndJ ] = NewLineSum;
32. short NewRectangleSum = RectangleSum + NewLineSum;
33. Matrix[ StartI ][ StartJ ][ EndI ][ EndJ ] = NewRectangleSum;
35. if( MaxSum < NewRectangleSum )
36. MaxSum = NewRectangleSum;
37. }
38. }
40. }
41. }
43. cout << MaxSum;
45. return 0;
46. }

크리에이티브 커먼즈 라이센스

이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리-동일조건변경허락 2.0 대한민국 라이센스에 따라 이용하실 수 있습니다.

"Algorithm" 분류의 다른 글

Algorithm Traning Book - 다섯번째 문제 (0)	2008/06/15
Algorithm Traning Book - 세 번째 문제 (0)	2008/06/10
Algorithm Traning Book - 두 번째 문제 (0)	2008/06/09
3n+1 Problem (0)	2008/02/17
The Blocks Problem (0)	2008/02/17

블로그는 귀차니즘

Maximum Sum

"Algorithm" 분류의 다른 글

트랙백 주소 :: http://www.filewiki.net/tc/trackback/6

Subject: Maximum sum

댓글을 달아 주세요

카테고리

최근에 올라온 글

최근에 달린 댓글

달력

링크

최근에 받은 트랙백

글 보관함

태그목록

« 2008/11 »
일	월	화	수	목	금	토
						1
2	3	4	5	6	7	8
9	10	11	12	13	14	15
16	17	18	19	20	21	22
23	24	25	26	27	28	29
30