1952. [모의 SW 역량테스트] 수영장

출처 

https://swexpertacademy.com/main/solvingProblem/solvingProblem.do

 

DFS를 사용하는 문제이지만

그리디 적으로 비용을 증가시키는 부분을 제외시켜서 DFS의 반복횟수를 줄이는 작업이 필요하다. 

 

#include<iostream>

using namespace std;


int day;
int month;
int tmonth;
int year;
int mina;
int result;

bool visit[13];
int mon[13];


void DFS(int cur)
{
	
	
	
	if(!visit[cur])
	{
		
		if(cur != 12)
		{
		
		
		
		
		if(mon[cur]*day < month)
		{
			
			result += mon[cur]*day;
			visit[cur] = true;
			
			DFS(cur+1);
			
			result -= mon[cur]*day;
			visit[cur] = false;
			
			
		}
		else
		{
			result += month;
			visit[cur] = true;
			
			DFS(cur+1);
			
			result -= month;
			visit[cur] = false;
			
			
			
			
		}
		
		
		if(cur == 11)
		{
			
			result += tmonth;
			visit[cur] = true;
			visit[cur+1] = true;
			
			DFS(cur+1);
			
			result -= tmonth;
			visit[cur] = false;
			visit[cur+1] = false;
			
		}
		else
		{
			
			result += tmonth;
			visit[cur] = true;
			visit[cur+1] = true;
			visit[cur+2] = true;
			
			DFS(cur+1);
			
			result -= tmonth;
			visit[cur] = false;
			visit[cur+1] = false;
			visit[cur+2] = false;
			
		}
		
		
		}
		else
		{
			if(mon[12]*day < month)
			{
				result += mon[12]*day;
				
				if(mina > result)
				{
					mina = result;
				}
				result -= mon[12]*day;
			}
			else
			{
				result += month;
				
				if(mina > result)
				{
					mina = result;
				}
				result -= month;
				
			}
			
			result += tmonth;
			
			if(mina > result)
				{
					mina = result;
				}
			result -= tmonth;
			
			
			
		}
		
		
		
		
		
		
		
		
		
	}
	else
	{
		
		if(!(cur==12))
		{
			
			DFS(cur+1);
		}
		else
		{
			
			if(result < mina)
			{
				mina = result;
			}
			
			
			
		}
		
	}
	

}





int main(void)
{
	
	
	int N;
	cin >> N;
	
	
	for(int tc = 1; tc <= N; tc++ )
	{
		
		mina = 987654321;
		result = 0;
		
		cin >> day >> month >> tmonth >> year;
		
		for(int i = 1; i<=12; i++)
		{
			
			cin >> mon[i];
			visit[i] = false;
		}
		
		
		if(mon[1]*day < month)
		{
			visit[1] = true;
			result += mon[1]*day;
			DFS(2);
			result -= mon[1]*day;
			visit[1] = false;
		}
		else
		{
			visit[1] = true;
			result += month;
			DFS(2);
			result -= month;
			visit[1] = false;

		}
		
			
		visit[1] = true;
		visit[2] = true;
		visit[3] = true;
		result += tmonth;
		DFS(4);
		result -= tmonth;
		visit[1] = false;
		visit[2] = false;
		visit[3] = false;
		
		if(mina > year)
		{
			mina = year;
		}
		
			
		
		cout << "#"<<tc<<" "<<mina<<endl;
		
		
		
	}
}