삼성 sw academy 9282. 초콜릿과 건포도

출처

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

SW Expert Academy

 

만약 문제가 자르는 것에 따른 부분합을 구해야 하는 문제다. => 누적합 알고리즘 , 메모이제이션 사용

필요 한 값을 미리 저장해 놓고 꺼내 쓰는 것임.

DFS로 풀었더니 시간초과가 발생해서 ,, 메모이제이션으로 풀었다.

 

#include<iostream>
#include<algorithm>
#include<string.h>

using namespace std;

int arr[51][51];
int sol[51][51]; // 부분합을 구하기 위해 1,1 부터 i,j까지의 합을 전부 기록 
int mini[51][51][51][51];
int N,M;

int solution(int y, int x, int posy, int posx)
{
	if(y == posy && x == posx) // 어차피 1x1 짜리 단위가 들어왔을 때는 더 이상 못자르므로 return
	{
		return 0;
	}
	
	if(mini[y][x][posy][posx])
	{
		return mini[y][x][posy][posx];
	}
	
	int cur = sol[posy][posx] - sol[y-1][posx] - sol[posy][x-1] + sol[y-1][x-1];
	
	
	int result = 987654321;
	for(int i = y; i < posy; i++) //가로에 대해 자를 때 자기가 자르는 시점의 영역 건포도에 잘라진 각 영역들을 계속 잘라가면서 진행 
	{
		int tmp = solution(y,x,i,posx) + solution(i+1,x,posy,posx); // 두 영역안에서도 각각 재귀로 잘라지고 잘라지면서 최소 값이 반환됨.
		// 최소 단위로 잘라진 곳부터 최소를 반환하므로 최소의 반환들로 이루어진 최소값임. 
		if(result > tmp + cur)
		{
			result = tmp + cur;
		}
	} 
	
	for(int j = x; j < posx; j++)
	{
		int tmp = solution(y,x,posy,j) + solution(y,j+1,posy,posx);
		if(result > tmp + cur)
		{
			result = tmp + cur;
		}
	}
	
	mini[y][x][posy][posx] = result;
	
	return result;
	
}

int main(void)
{
	int T;
    cin >> T;
 
    for (int tc = 1; tc <= T; tc++)
	{
    	
		cin >> N >> M;
		memset(mini, 0, sizeof(mini));
		
		for(int i = 1; i <= N; i++)
		{
			for(int j = 1; j <= M; j++)
			{
				cin >> arr[i][j];
			}
		}
		
		for(int i = 1; i <= N; i++)
		{
			for(int j = 1; j <= M; j++)
			{
				sol[i][j] = sol[i-1][j] + sol[i][j-1] - sol[i-1][j-1] + arr[i][j];
			}
		}
		
		int result = solution(1,1,N,M);
		
		cout <<"#"<<tc<<" "<<result << endl;
        
    }
	
	
	
}

 

 

 

DFS로 구현 (시간초과 발생)

#include<iostream>

using namespace std;

int arr[51][51];
bool col[50];
bool row[50];

int mina = 987654321;
int cur;
int N,M;

int calrow(int idx)
{
	int minidx = idx;
	int maxidx = idx;
	
	while(minidx > 0)
	{
		minidx--;
		if(row[minidx])
		{
			break;
		}
	}
	
	
	while(maxidx < N)
	{
		maxidx++;
		if(row[maxidx])
		{
			break;
		}
	}
	
	
	int sum = 0;
	
	for(int i = minidx+1; i <= maxidx; i++ )
	{
		for(int j = 1; j <= M; j++)
		{
			sum += arr[i][j];
		}
		
	}
	
	
	return sum;
}


int calcol(int idx)
{
	int minidx = idx;
	int maxidx = idx;
	
	while(minidx > 0)
	{
		minidx--;
		if(col[minidx])
		{
			break;
		}
	}
	
	
	while(maxidx < M)
	{
		maxidx++;
		if(col[maxidx])
		{
			break;
		}
	}
	
	
	int sum = 0;
	for(int i = minidx+1; i <= maxidx; i++)
	{
		for(int j = 1; j <= N; j++)
		{
			sum += arr[j][i];
		}
	}
	
	return sum;
}




void DFS(int cut)
{
	if(cut == (N-1)+(M-1))
	{
		if(cur < mina)
		{
			mina = cur;
		}
		
		return;
	}
	
	
	for(int i = 1; i <= N-1; i++)
	{
		if(!row[i])
		{
			row[i] = true;
			int caly = calrow(i);
			cur += caly;
			DFS(cut+1);
			cur -= caly;
			row[i] = false;
		}
	}
	
	for(int i = 1; i <= M-1; i++)
	{
		if(!col[i])
		{
			col[i] = true;
			int calx = calcol(i);
			cur += calx;
			DFS(cut+1);
			cur -= calx;
			col[i] = false;
		}
	}
}


int main(int argc, char** argv)
{
	int test_case;
	int T;

	cin>>T;
	/*
	   여러 개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
	*/
	for(test_case = 1; test_case <= T; ++test_case)
	{
		
		cin >> N >> M;
		mina = 987654321;
		cur = 0;
		
		for(int i = 1; i <= N; i++)
		{
			for(int j = 1; j <= M; j++)
			{
				cin >> arr[i][j];
			}
		}
		
		DFS(0);
		
		cout <<"#"<<test_case<<" "<< mina << endl;

	}
	return 0;//정상종료시 반드시 0을 리턴해야합니다.
}