[BOJ] 4095 최대 정사각형(DP) , 11660 구간 합 구하기 5(DP)

www.acmicpc.net/problem/4095

4095번: 최대 정사각형

www.acmicpc.net/problem/11660

11660번: 구간 합 구하기 5

두 문제의 공통점은 사각형(행렬)에서 dp를 사용해야 한다는 것인데, 이 경우에 dp[i][j]의 값을 얻기 위해서는 다음과 같은 점화식 꼴을 필요로 한다. 

dp[i][j] = Function(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + etc

dp의 두가지 요소(점화식, 초기값)은 행렬(사각형) dp의 특징을 살려 쉽게 정할 수 있다.  

 

1) 일반적인 행렬의 읽기 순서대로 점화식에 따른 dp값을 얻을 수 있다.

2) dp의 초기값을 모아두기 위해 정적 배열에 0의 값을 담아둘 1칸의 여유를 둔다.

1) 4095 최대 정사각형

주제: DP

시간복잡도: O(N*M) 

점화식:

코드:

#include<bits/stdc++.h>

using namespace std;

int main()
{
	//scanf를 쓸 거면 지운다  
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	
	while(1)
	{
		int n, m;
		int big = 0;
		cin >> n >> m;
		
		if(n == 0 && m == 0) return 0;
	
		int dp[n+1][m+1];
		
		memset(dp, 0, sizeof(dp));
		
		for(int i = 1; i <= n; i++)
		{
			for(int j = 1; j <= m; j++)
			{
				int x;
				cin >> x;
				
				if(x == 1)
				{	
					dp[i][j] = min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]}) + 1;
					
					big = max(big , dp[i][j]);	
				}
			}
		}
		
		cout << big << '\n';
	}

	return 0;
}

2) 11660 구간 합 구하기 5

주제: DP

시간복잡도: O(N^2) 

점화식:

코드:

#include<bits/stdc++.h>

using namespace std;

int main()
{
	int N, M;
	
	cin >> N >> M;
	
	vector<int> answer;
	
	int dp[N+1][N+1];

	for(int i = 1 ; i <= N; i++)
	{
		for(int j = 1; j <= N; j++)
		{
			int n;
			cin >> n;
			dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + n;		
		}	
	} 	

	while(M--)
	{	

		int x1, y1, x2, y2;
		cin >> x1 >> y1;
		cin >> x2 >> y2;
		
		int num = dp[x2][y2] - dp[x2][y1-1] - dp[x1-1][y2] + dp[x1-1][y1-1];	
		answer.push_back(num);
	}
	
	for(int i : answer)
	{
		cout << i << '\n';
	}
}

요약: 

행렬(사각형) DP의 경우, 점화식을 얻는 방식이 대부분 비슷하고, 행렬을 읽는 방식대로 DP값을 얻을 수 있는 DOWN-TOP방식이 가능하므로 쉽게 정리된 코드를 얻을 수 있다. 

dp[i][j] = Function(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + etc

위의 방식은 외워 두는 것이 좋고, 합집합을 구하는 원리가 들어갈 수 있다. (cf, 합집합(A, B) = A + B - 교집합(A, B) )

얻을 수 있는 다른 팁:

세 수의 크기를 비교하는 방법을 주로 min( min(a, b) , c )로 코드를 짜곤 했는데, min( {a, b, c} ) 로 짜는 방법이 더 좋음을 알 수 있었다.