[c++] 영지선택 small, large

영지선택 small

#include <iostream>
#include <vector>
#include <algorithm>

/* run this program using the console pauser or add your own getch, system("pause") or input loop */
using namespace std;
int a[6][51];
int main() {
	freopen("input.txt", "rt", stdin);
	int i, j, k, l, h, w, sh, sw, max=-2147000000, sum;
	scanf("%d %d", &h, &w);
	for(i=1; i<=h; i++){
		for(j=1; j<=w; j++){
			scanf("%d", &a[i][j]);
		}
	}
	scanf("%d %d", &sh, &sw);
	for(i=1; i<=h-sh+1; i++){
		for(j=1; j<=w-sw+1; j++){
			sum=0;
			for(k=i; k<i+sh; k++){
				for(l=j; l<j+sw; l++){
					sum+=a[k][l];
				}
			}
			if(sum>max) {
				max=sum;	
			}
		}
	}
	printf("%d", max);
	return 0;
}

<배열다르게 선언한 것>
#include <iostream>
#include <vector>
#include <algorithm>

/* run this program using the console pauser or add your own getch, system("pause") or input loop */
using namespace std;
//int a[6][51];
int main() {
	//freopen("input.txt", "rt", stdin);
	int i, j, k, l, h, w, sh, sw, max=-2147000000, sum;
	scanf("%d %d", &h, &w);
	vector<vector<int> > a(h+1, vector<int>(w+1, 0));
	for(i=1; i<=h; i++){
		for(j=1; j<=w; j++){
			scanf("%d", &a[i][j]);
		}
	}
	scanf("%d %d", &sh, &sw);
	for(i=1; i<=h-sh+1; i++){
		for(j=1; j<=w-sw+1; j++){
			sum=0;
			for(k=i; k<i+sh; k++){
				for(l=j; l<j+sw; l++){
					sum+=a[k][l];
				}
			}
			if(sum>max) {
				max=sum;	
			}
		}
	}
	printf("%d", max);
	return 0;
}

처음에 문제에서 배열의 개수를 잘못보아서(?)

배열을 작게 선언했다. 배열을 작게 선언하니 당연히 그 배열보다 큰 input이 들어오니 timelimit가 났다.

메모리가 상관없다면 차라리 vector로 선언해서 0으로 초기화 하는게 나을 수도 있겠다.

timelimit가 나면 배열의 크기도 살펴보자

 

영지선택 large

#include <iostream>
#include <vector>
#include <algorithm>

/* run this program using the console pauser or add your own getch, system("pause") or input loop */
using namespace std;
//int a[6][51];
int main() {
	//freopen("input.txt", "rt", stdin);
	int i, j, k, l, h, w, sh, sw, max=-2147000000, sum;
	scanf("%d %d", &h, &w);
	vector<vector<int> > a(h+1, vector<int>(w+1, 0));
	vector<vector<int> > dy(h+1, vector<int>(w+1, 0));
	for(i=1; i<=h; i++){
		for(j=1; j<=w; j++){
			scanf("%d", &a[i][j]);
			dy[i][j]=dy[i-1][j]+dy[i][j-1]-dy[i-1][j-1]+a[i][j];
		}
	}
	scanf("%d %d", &sh, &sw);
	
	for(i=sh; i<=h; i++){
		for(j=sw; j<=w; j++){
			sum=dy[i][j]-dy[i-sh][j]-dy[i][j-sw]+dy[i-sh][j-sw];
			if(sum>max) {
				max=sum;	
			}
			sum=0;
		}
	}
	printf("%d", max);
	return 0;
}