48강~51강

48강

• 48강 내용은 혼자 풀 수 있었다.

cf) 정수를 나눗셈을 하고 반올림을 처리하기를 원하는 경우에는 0.5를 더해주면 된다.

49강

• 49강 내용은 혼자 풀 수 있었다.

cf) 2차원 배열의 경우 행을 먼저 처리하고, 열을 처리 할 때, 행에 대해서 먼저 처리를 하고 열에 대해서 처리를 하여 덮어씌우는 느낌으로 하면 더 쉽게 풀 수 있다. 마치 and 연산처럼

51강

문제

내풀이

#include <stdio.h>
#include <algorithm>
#include <vector>
#include <iostream>
#include <math.h>
using namespace std;
int main(){
	//freopen("input.txt", "rt", stdin);
	int h,w;
	int hidx=0;
	int widx=0;
	int sh,sw;
	int sum=0;
	int max=-214000000;
	scanf("%d %d",&h,&w);
	vector<vector<int> > map(h,vector<int>(w,0));
	for(int i=0; i<h ; i++)
    {
		for(int j=0;j<w;j++)
        {
			scanf("%d",&map[i][j]);
		}
	}
   
	scanf("%d %d",&sh,&sw);
	vector<vector<int> > calc(h,vector<int>(w-sw+1,0));
	for(int i=0; i < h ; i++){
		for(int l=0; l < sw ; l++){
			sum+=map[hidx][widx++];
		}
		calc[i][0]=sum;
		for(int j=1; j < w-sw+1 ; j++){
			calc[i][j]=calc[i][j-1]-map[i][j-1]+map[i][j+sw-1];
			sum=0;
		}
		widx=0;
		hidx++;
	}

	hidx=0;
	widx=0;
	vector<vector<int> > result(w-sw+1,vector<int>(h-sh+1,0));
	for(int i=0 ; i < calc[0].size() ; i++){
		for(int l=0; l < sh ; l++ ){
			sum += calc[hidx++][widx];
		}
		result[i][0]=sum;
		if(max < result[i][0] ) max=result[i][0];
		for(int j=1 ; j < calc.size()-sh+1 ;j++){
			result[i][j]=result[i][j-1]-calc[j-1][i]+calc[j+sh-1][i];
			if(max < result[i][j] ) max=result[i][j];
			sum=0;
		}
		hidx=0;
		widx++;
	}
	
	cout << max;
}

정석풀이

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
int a[701][701], dy[701][701];
int main(){
	freopen("input.txt", "rt", stdin);
	int h, w, n, m, i, j, tmp, max=-2147000000;
	scanf("%d %d", &h, &w);
	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", &n, &m);
	for(i=n; i<=h; i++){
		for(j=m; j<=w; j++){
			tmp=dy[i][j]-dy[i-n][j]-dy[i][j-m]+dy[i-n][j-m];
			if(tmp>max) max=tmp;		
		}
	}
	printf("%d\n", max);
	return 0;
}

• 풀이의 길이나 수행속도 코드가 읽기 좋은가 하는 부분 모두에서 별로 좋지 못한 코딩을 했다고 생각을 한다.
• 이 문제 같은 경우는 이차원 배열에 특정 영역의 값의 합을 구해서 해당 값을 비교하여 최대값을 찾는 문제였다.
• 먼저 2차원 배열에 입력값을 다 받는다. 그리고 이 문제의 경우 DP를 사용한다. 2차원의 dp배열에 각 인덱스를 오른쪽 모서리 끝으로 하는 사각형을 그려서 해당 사각형 안에 들어가는 인덱스의 값을 모두 더하여 dp배열에 저장한다.
• 이렇게 저장된 dp배열을 통해서 영역의 값을 구할 수 있는데 그 방법은 밑에 그림을 보면 쉽게 알 수 있다.
  
  지금 현재 빨간 부분의 값을 알고 싶은 것인데, 이 경우에 네모칸 전체영역의 값은 빨간색 모서리 부분의 인덱스 일것이다. 그 인덱스의 값에서 각각의 파란색 사각형 오른쪽아래 모서리의 인덱스의 값을 빼고 그리고 초록색깔 영역의 오른쪽 아래 모서리의 인덱스 값을 더하게 되면 원하는 빨간색 영역의 값을 구할 수 있게되는 것이다.