문제 11, 동맹 휴업(Hartal)

PC/UVa ID : 110203/10050

개요

특정 기간 N일 동안, 동맹 휴업을 하는 정당들의 휴업일 총 수를 구하라는 것이다. 정당들의 수를 P라고 했을 때, 정당들의 휴업 지수를 각 h1 h2 .. 라고 한다. 이 휴업지수는 그 지수일자 만큼 일 한 뒤에 1번 쉰다는 뜻이다.

특정 기간 N일 중 1일 째는 무조건 일요일이며, 예외적으로 금요일, 토요일에는 휴업을 하지 않는다. .

여기까지 일반적인 설명이고, 자세한것은 링크를 보길 바란다.

예 )
http://blog.naver.com/nam_s_y/140039960770
http://talsu.net/125
http://www.programming-challenges.com/pg.php?page=downloadproblem&probid=110203&format=html
http://deren.tistory.com/82

입력

1. 입력의 첫번째는 테스트 케이스 갯수를 받는다.
   
2. 다음줄에는 시뮬레이션 돌릴 기간 N을 받으며, 7일 ~ 3650일 까지만 받는다.
   
3. 그 다음줄에는 참여할 정당들의 수 P를 받는다. 1 ~ 100 까지 받을 수 있다.
   
4. 그 다음줄에는 P의 갯수 만큼의 휴업 지수를 입력받는다. 휴업 지수는 양의 정수만 된다.
   

출력

모든 입력이 끝나면, 바로 출력한다.

-- 특정 기간 동안 동맹휴업일수가 몇일 있는지 체크 하는 함수. function simulation( days, PoliticalPartys ) -- 모든 정당들의 동맹휴업 지수를 이용하여, 동맹 휴업일수를 모두 -- 조사한다. 조사 할 때, 중복체크도 함께 하기 위하여 table의 키를 썼다. HartalDays = {} for PoliticalParty, HartalParameter in pairs( PoliticalPartys ) do for i = 1, days / HartalParameter, 1 do HartalDays[i * HartalParameter] = i * HartalParameter end end -- 모든 정당의 휴일에서 금요일(day % 7 == 6), 토요일(day % 7 == 0) 일짜를 빼준다. RealHartalDays = {} for HartalDay in pairs( HartalDays ) do day = HartalDay % 7 if 0 ~= day and 6 ~= day then table.insert( RealHartalDays, HartalDay ) end end -- 누적된 테이블의 요소의 갯수를 새어서, 리턴한다. return #RealHartalDays end function main( ) -- 동맹 휴업 케이스를 입력 받는다. NumOfCase = io.read() NumOfCase = tonumber(NumOfCase) if nil == NumOfCase then print("The NumOfCase is Invalid!") return end -- 시뮬레이션 할 날짜를 받는다. SimulationDays = io.read() SimulationDays = tonumber(SimulationDays) if nil == SimulationDays then print("The SimulationDays of day is Invalid!") return end if 7 > SimulationDays or 3650 < SimulationDays then print("The SimulationDays of day is Invalid!") return end -- 정당의 갯수를 받는다. NumOfPoliticalParty = io.read() NumOfPoliticalParty = tonumber( NumOfPoliticalParty ) if nil == NumOfPoliticalParty or 1 > NumOfPoliticalParty or 100 <NumOfPoliticalParty then print("The NumOfPoliticalParty is Invalid!") return end -- 각 정당당 동맹휴업 지수를 입력 받는다. ParticalPartys = {} for i = 1, NumOfPoliticalParty, 1 do HartalParameter = io.read() HartalParameter = tonumber( HartalParameter ) if nil ~= HartalParameter then table.insert( ParticalPartys, HartalParameter ) end end print( simulation( SimulationDays, ParticalPartys ) ) end main()

C++

#include <boost/foreach.hpp> #include <vector> #include <map> #include <iostream> // 기간 중 동맹 휴일을 시뮬레이션하여, 그 휴일 일수를 리턴해 준다. int simulation( const int days, std::vector<int>& PoliticalPartys ) { // 모든 정당당 동맹 휴일 일짜를 조사하여, 동맹 휴일이 될수 있을 경우 // 해당 날짜를 map의 키로써 중복되도 상관없게 밀어 넣는다. std::map<int, int> hartalholydays; BOOST_FOREACH( int hartalparameter, PoliticalPartys ) { for( int i = 1; i <= days / hartalparameter; ++i) { // 금요일과 토요일은 휴일날짜에서 7로 나누었을 때 , // 나머지가 6이거나 0일경우 를 뜻한다. int holyday = hartalparameter * i % 7; if( holyday != 0 && holyday != 6) hartalholydays.insert( std::make_pair( hartalparameter * i, holyday ) ); } } // 동맹 휴일 갯수를 리턴한다. return hartalholydays.size(); } int main( void ) { int case_num = 0; std::cin >> case_num; for( int i = 0; i < case_num; ++i ) { int Simulation_Days = 0; std::cin >> Simulation_Days; int PoliticalParty_num = 0; std::cin >> PoliticalParty_num; std::vector<int> PoliticalPartys; PoliticalPartys.resize( PoliticalParty_num ); BOOST_FOREACH(int &HartalParameter, PoliticalPartys ) { std::cin >> HartalParameter; } std::cout << simulation( Simulation_Days, PoliticalPartys ) << std::endl; } return 0; }