블로그는 귀차니즘 :: Ecological Bin Packing

문제링크 : http://icpcres.ecs.baylor.edu/onlinejudge/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=38
의 견 : 나올 수 있는 경우의 수는 3! 개 입니다. 즉, 경우의 수가 적으므로 6가지 경우에 대한 측정값들을 수동으로 계산하여 출력할 수 있습니다. 하지만, 일반적으로 계산을 해보고자 하는 마음으로 priority_queue와 string을 짝으로 조합하여 구현을 했습니다.
소스
103.cpp (Language : cpp)
1. #include <iostream>
2. #include <queue>
3. #include <string>
5. struct SortNode {
6. int Total;
7. std::string OutputStr;
8. };
10. bool operator < ( const SortNode &Left, const SortNode &Right )
11. {
12. size_t LeftLength = Left.OutputStr.length();
13. size_t RightLength = Right.OutputStr.length();
15. if( ( Left.Total == Right.Total ) && ( LeftLength == RightLength ) ) {
16. for( int i = 0; i < 3; i++ ) {
18. char LeftChar = Left.OutputStr[ i ];
19. char RightChar = Right.OutputStr[ i ];
21. if( LeftChar == RightChar )
22. continue;
23. else if( LeftChar > RightChar )
24. return true;
25. else
26. return false;
27. }
28. }
30. return ( Left.Total > Right.Total );
31. }
33. int main( int argc, char **argv )
34. {
35. unsigned int Bottle[ 9 ] = { 0, };
37. while( std::cin >> Bottle[ 0 ] >> Bottle[ 1 ] >> Bottle[ 2 ] >> Bottle[ 3 ] >> Bottle[ 4 ] >> Bottle[ 5 ] >> Bottle[ 6 ] >> Bottle[ 7 ] >> Bottle[ 8 ] ) {
38. std::priority_queue< SortNode > BackTracking;
40. SortNode Temp;
41. Temp.Total = 0;
42. BackTracking.push( Temp );
44. while( true ) {
46. SortNode ProcessNode = BackTracking.top();
47. BackTracking.pop();
49. size_t ProcessStrLength = ProcessNode.OutputStr.length();
51. if( ProcessStrLength == 3 ) {
52. std::cout << ProcessNode.OutputStr << " " << ProcessNode.Total << std::endl;
53. break;
54. }
56. ProcessStrLength *= 3;
58. if( ProcessNode.OutputStr.find( "C" ) == UINT_MAX ) {
59. SortNode CNode( ProcessNode );
61. CNode.Total += ( Bottle[ ProcessStrLength ] + Bottle[ ProcessStrLength + 1 ] );
62. CNode.OutputStr += "C";
64. BackTracking.push( CNode );
65. }
67. if( ProcessNode.OutputStr.find( "G" ) == UINT_MAX ) {
68. SortNode GNode( ProcessNode );
70. GNode.Total += ( Bottle[ ProcessStrLength ] + Bottle[ ProcessStrLength + 2 ] );
71. GNode.OutputStr += "G";
73. BackTracking.push( GNode );
74. }
76. if( ProcessNode.OutputStr.find( "B" ) == UINT_MAX ) {
77. SortNode BNode( ProcessNode );
79. BNode.Total += ( Bottle[ ProcessStrLength + 1 ] + Bottle[ ProcessStrLength + 2 ] );
80. BNode.OutputStr += "B";
82. BackTracking.push( BNode );
83. }
84. }
85. }
87. return 0;
88. }

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

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

"Algorithm" 분류의 다른 글

Dovelet - (1) (0)	2010/03/13
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

블로그는 귀차니즘

Ecological Bin Packing

"Algorithm" 분류의 다른 글

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

댓글을 달아 주세요

카테고리

최근에 올라온 글

최근에 달린 댓글

달력

링크

최근에 받은 트랙백

글 보관함

태그목록

« 2010/03 »
일	월	화	수	목	금	토
	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	31