Skip to content

algorithm adventures in moving part iv

Jump to bottom
Jongbin Oh edited this page Jun 8, 2013 · 1 revision

Outbreak

문제 요약

  • 최대 10000Km 거리의 목표지 까지 최소의 기름값을 쓰면서 도착하는 방법은?

문제 해결

  • 최대 10000 + 1 + 100 Km 를 인덱스로 DP 테이블을 만듬.
  • 각 위치에서의 최소 기름값을 구해서 DP 테이블 완성
  • DP 테이블을 돌면서 기름값을 누적 시켜나가 답을 구한다.

소감

  • Wrong 한번, Presentation Error 한번, Solved.. 오 럭키!
  • 입출력이 까탈스럽네요;

풀이

    // "Adventures in Moving - Part IV" Solution By Outbreak 
    
    #include <iostream>
    #include <vector>
    
    using namespace std;
    
    //#define _TDD
    
    //--------------------------------------------------------------------
    
    namespace Solver
    {
    	static const int IMPOSSIBLE_PRICE = 10000;
    	static const int MAX_DISTANCE = 10001;
    	static const int MAX_GAS_SIZE = 200;
    	static const int DEFAULT_GAS_SIZE = 100;
    
    	static vector<int> VPrice(MAX_DISTANCE+DEFAULT_GAS_SIZE,IMPOSSIBLE_PRICE);
    
    	// 1. > DP 테이블 초기화
    	void MakePriceTable()
    	{
    		int i;
    
    		for( i=0; i<MAX_DISTANCE+DEFAULT_GAS_SIZE; i++ )
    		{
    			VPrice[i] = IMPOSSIBLE_PRICE;
    		}
    
    		for( i=0; i<=DEFAULT_GAS_SIZE; i++ )
    		{
    			VPrice[i] = 0;
    		}
    	}
    
    	// 2. > DP 테이블 만들기 - 각 주유소를 중심으로!
    	void InsertPrice( int dist, int price )
    	{
    		// 현재 위치에서 제일 싼 가격
    		for(int i=1;i<=MAX_GAS_SIZE;i++)
    		{
    			if(VPrice[ dist+i ] > price)
    			{
    				VPrice[ dist+i ] = price;
    			}
    		}
    	}
    
    	// 3. > 최소 비용 구하기
    	int CalcMinimumPrice(int distance)
    	{
    		int price = 0;
    
    		// 각 위치에서의 주유 가격을 더해 나가면서 총 비용을 산출한다.
    		// 반납 시 기름통의 반이 채워져 있어야 하므로 그 만큼을 더 간다고 생각한다.
    		for(int i=1; i<=distance+DEFAULT_GAS_SIZE; i++) 
    		{
    			if (VPrice[i] == IMPOSSIBLE_PRICE) 
    			{
    				return -1;
    			}
    
    			price += VPrice[i];
    		}
    
    		return price;
    	}
    }
    
    //--------------------------------------------------------------------
    
    namespace Runner
    {
    	void Execute(istream& in, ostream& out)
    	{	
    		int sample = 0;
    
    		in >> sample;
    
    		while( sample-- )
    		{
    			int distance = 0, dist = 0, price = 0;
    
    			in >> distance;
    
    			Solver::MakePriceTable();
    			
    			while(true)
    			{		
    				in.get();
    
    				// 개행이 한개 더오면 다음 샘플 처리
    				if( in.peek() == '\n')
    				{
    					break;
    				}
    
    				in >> dist >> price;					
    
    				if( in.fail() )
    					break;
    
    				Solver::InsertPrice(dist, price);
    			}
    
    			int result = Solver::CalcMinimumPrice(distance);
    
    			if( result == -1 )
    			{
    				out << "Impossible" << endl;
    			}
    			else
    			{
    				out << result << endl;
    			}
    
    			if( sample > 0 )
    			{
    				out << endl;
    			}
    		}
    	}
    }
    
    
    //--------------------------------------------------------------------
    
    #ifdef _TDD
    
    #include "unittest++.h"
    
    struct TEST_BASE
    {
    	stringstream input;
    	stringstream output;
    };
    
    TEST_FIXTURE(TEST_BASE, PresentationTest)
    {
    	input << 
    		"2\n"
    		"\n"
    		"500\n"
    		"100 999\n" 
    		"150 888\n"
    		"200 777\n"
    		"300 999\n"
    		"400 1009\n"
    		"450 1019\n"
    		"500 1399\n";
    
    	input << "\n";
    
    	input << 	
    		"500\n"
    		"100 999\n" 
    		"150 888\n"
    		"200 777\n"
    		"300 999\n"
    		"400 1009\n"
    		"450 1019\n"
    		"500 1399\n";
    
    	Runner::Execute(input, output);
    
    	CHECK_EQUAL( "450550\n\n450550\n", output.str());
    }
    #endif
    
    //--------------------------------------------------------------------
    
    int main()
    {
    
    #ifdef _TDD	
    	UnitTest::RunAllTests();
    #else
    	Runner::Execute(cin, cout);
    #endif // _TDD
    	return 0;
    }

ParkPD

  • 주유소 들릴 때마다 항상 탱크를 꽉 채워야 한다는 가정이 있다면 이것도 답이 될 수 있겠지만, 역시 무엇을 DP table 로 만들 것인가를 잘 못 생각했네요. 쩝...

  • 새로 푼 문제는 준석씨랑 똑같이 풀었기 때문에 따로 올리지 않습니다. :)

  • 그러니까 아래 코드는 잘 못 푼 거라는 거.. T_T

      /* @JUDGE_ID:parkpd 110401 Cpp "test" */
  
  /* @BEGIN_OF_SOURCE_CODE */
  
  #include <iostream>
  #include <vector>
  #include <set>
  #include <deque>
  #include <list>
  #include <stack>
  #include <string>
  #include <algorithm>
  #include <map>
  #include <limits>
  #include <assert.h>
  #include <iomanip>
  #include <math.h>
  
  #define _UNIT_TEST
  
  #ifdef _UNIT_TEST
  #include <Windows.h>
  #endif
  
  using namespace std;
  
  namespace ATUtil
  {
  	bool IsInRange(int value, int from, int to)
  	{
  		return (from <= value) && (value <= to);
  	}
  
  	int ConvertToIndex(char c)
  	{
  		if ('a' <= c && c <= 'z')
  		{
  			return c - 'a';
  		}
  		else
  		{
  			return -1;
  		}
  	}
  
  	char ConvertToChar(int i)
  	{
  		return (char)i + 'a';
  	}
  
  #ifdef _UNIT_TEST
  	class CStopWatch
  	{
  	public:
  		CStopWatch()
  		{
  			m_StartTick = GetTickCount();		// gcc 에서 안 될 수 있으니까
  		}
  
  		~CStopWatch()
  		{
  			cout << "Time passed : " << GetTickCount() - m_StartTick << " milisec.\n";
  		}
  
  		int m_StartTick;
  	};
  #endif
  
  	typedef map<int, int> IntDB;
  	typedef vector<int> Ints;
  	typedef list<int> IntList;
  
  };
  
  using namespace ATUtil;
  
  #ifdef _UNIT_TEST
  
  #include "../UnitTest++/src/UnitTest++.h"
  
  #ifdef max
  #undef max
  #endif
  
  #ifdef min
  #undef min
  #endif
  
  int main()
  {
  	UnitTest::RunAllTests();
  
  	char temp;
  	cin >> temp;
  
  	return 0;
  }
  
  #endif
  
  // code implement
  
  namespace ATCode
  {
  	//////////////////////////////////////////////////////////////////////////
  	// CStation
  	class CStation
  	{
  	public:
  		CStation(int d, int c) : m_Dist(d), m_Cost(c), m_TotalCost(0) {}
  
  		int m_Dist;
  		int m_Cost;
  		int m_TotalCost;
  	};
  
  	//////////////////////////////////////////////////////////////////////////
  	// CStationNavi
  	class CStationNavi
  	{
  	public:
  		enum {MAX_STATIONS = 9};
  
  		// 100 이상의 연료를 남기기 위해, 아예 거리를 늘려준다.
  		CStationNavi(int dist) : m_Dist(dist + 100)
  		{
  			// 출발지도 일종의 주유소로 생각하자.
  			// 미리 가지고 있는 가스 100 만큼을 뺀 거리에서 가스 200 을 채웠다고 생각하고 시작한다.
  			Input(-100, 0);
  		}
  
  		void Input(int d, int c) 
  		{
  			m_Stations.push_back(CStation(d, c));
  		}
  
  		template<typename InputIterator>
  		void Inputs(InputIterator f, InputIterator t) 
  		{
  			for (InputIterator i = f; i < t; i += 2)
  			{
  				Input(*i, *(i+ 1));
  			}
  		}
  
  		int CalcDirectCost(int from, int to)
  		{
  			if (-1 == m_CostTable[from][to])
  			{
  				const int distBetweenStation = m_Stations[to].m_Dist - m_Stations[from].m_Dist;
  				if (200 < distBetweenStation)
  				{
  					m_CostTable[from][to] = numeric_limits<int>::max();	// 갈 수 없음.
  				}
  				else
  				{
  					m_CostTable[from][to] = m_Stations[from].m_Cost * (distBetweenStation);
  				}
  			}
  
  			return m_CostTable[from][to];
  		}
  
  		int CalcCost(int from, int to)
  		{
  			// TODO : 가스가 부족하면 무한대를 리턴해야 한다. 어떻게?
  
  			// Cs-t = min(Cs-t, min(k=s-t)(Cs-k, Ck-t))
  			if ((from == to) || (from + 1 == to))
  			{
  				return CalcDirectCost(from, to);
  			}
  			else
  			{
  				// Cs-t = min(Cs-t, min(k=s-t)(Cs-k, Ck-t))
  				int minCost = numeric_limits<int>::max();
  				for (int k = from + 1; k < to; ++k)
  				{
  					int cost = CalcCost(from, k) + CalcCost(k, to);
  					if (cost < minCost)
  					{
  						minCost = cost;
  					}
  				}
  
  				m_CostTable[from][to] = min(CalcDirectCost(from, to), minCost);
  				return m_CostTable[from][to];
  			}
  		}
  
  		int Calc()
  		{
  			Input(m_Dist, 0);		// 목적지도 일종의 주유소로 생각하자.
  
  			// Cs-t = min(Cs-t, min(k=s-t)(Cs-k, Ck-t))
  
  			// case 1.
  			// C0-2 = min(C0-2, C0-1 + C1-2)
  
  			for (int r = 0; r < MAX_STATIONS; ++r)
  			{
  				for (int c = 0; c < MAX_STATIONS; ++c)
  				{
  					if (r == c)
  					{
  						m_CostTable[r][c] = 0;
  					}
  					else
  					{
  						m_CostTable[r][c] = -1;
  					}
  				}
  			}
  
  			const int numStations = (int)m_Stations.size();
  			int calcCost = 0;
  			for (int diagonal = 1; diagonal <= numStations; ++diagonal)
  			{
  				for (int r = 0; r < numStations - diagonal; ++r)
  				{
  					int c = r + diagonal;
  					//cout << r << c << "\n";
  					//m_CostTable[r][c] = 
  						//min(m_CostTable[r][c], 
  							//min(k)(m_CostTable[r][k] + m_CostTable[k][c]);
  					calcCost = CalcCost(r, c);
  					m_CostTable[r][c] = calcCost;
  				}
  			}
  			
  			return m_CostTable[0][numStations - 1];
  		}
  
  		int m_Dist;
  		vector<CStation> m_Stations;
  
  		int m_CostTable[MAX_STATIONS][MAX_STATIONS];
  	};
  
  	///////////////////////////////////////////////////////////////
  	// CConsole
  	class CConsole
  	{
  	public:
  		static void ConsoleTest(istream& input, ostream& output);
  	};
  
  	void CConsole::ConsoleTest(istream& input, ostream& output)
  	{
  		int testCount = 0;
  		input >> testCount;
  
  		for (int i = 0; i < testCount; ++i)
  		{
  			if (1 <= i)
  			{
  				output << "\n";
  			}
  
  			int dist;
  			input >> dist;
  
  			CStationNavi navi(dist);
  
  			int pos, price;
  			while (input >> pos >> price)
  			{
  				navi.Input(pos, price);
  			}
  
  			output << navi.Calc() << "\n";
  		}
  	};
  
  }
  
  using namespace ATCode;
  
  #ifndef _UNIT_TEST
  
  int main()
  {
  	CConsole::ConsoleTest(cin, cout);
  
  	return 0;
  }
  
  #else
  
  // tests
  
  struct FixtureBase
  {
  	FixtureBase()
  	{
  	}
  
  	stringstream input;
  	stringstream output;
  };
  
  TEST_FIXTURE(FixtureBase, Case2)
  {
  	int stations[] = {100, 999, 200, 1000};
  	CStationNavi n(300);
  	n.Inputs(&stations[0], &stations[sizeof(stations) / sizeof(int)]);
  	CHECK_EQUAL(0, n.Calc());
  }
  
  TEST_FIXTURE(FixtureBase, Case1)
  {
  	int stations[] = {50, 999};
  	CStationNavi n(100);
  	n.Inputs(&stations[0], &stations[sizeof(stations) / sizeof(int)]);
  	CHECK_EQUAL(0, n.Calc());
  }
  
  TEST_FIXTURE(FixtureBase, ConsoleTest)
  {
  	input << 
  		"1\n"
  		"\n"
  		"500\n"
  		"100 999\n"
  		"150 888\n"
  		"200 777\n"
  		"300 999\n"
  		"400 1009\n"
  		"450 1019\n"
  		"500 1399\n";
  	CConsole::ConsoleTest(input, output);
  	CHECK_EQUAL( 
  		"450550\n", 
  		output.str());
  }
  
  #endif
  
  /* @END_OF_SOURCE_CODE */
Clone this wiki locally