Problem Solving/SWEA
SWEA 2001번: 파리 퇴치/DP
이진2
2021. 1. 16. 00:51
SW Expert Academy
SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!
swexpertacademy.com
N과 M이 주어졌을 때
N*N배열에서, M*M의 부분합이 가장 큰 구간을 찾는 문제
부분합은 뭐다? DP다
그렇기 때문에 원래 배열의 값을 저장하는 array배열, (0,0)~(n,n)의 직사각형 합을 저장하는 sum배열 두 개를 선언했다
특정 좌표의 sum 값은
sum(i,j) = sum(i-1,j) + sum(i,j-1) - sum(i-1,j-1)로 구해줬다
직사각형 배열에서 어느 부분이 중복 계산될지 체크하면 풀 수 잇는 문제 !!
import java.util.Scanner;
import java.io.FileInputStream;
class Solution
{
public static void main(String args[]) throws Exception
{
Scanner sc = new Scanner(System.in);
int T;
T=sc.nextInt();
for(int test_case = 1; test_case <= T; test_case++)
{
int ans=0;
String s=sc.nextLine();
int n=sc.nextInt(),m=sc.nextInt();
int[][] arr=new int[20][20], sum=new int[20][20];
for(int i=1;i<=n;i++) {
for (int j = 1; j <= n; j++) {
arr[i][j] = sc.nextInt();
sum[i][j] = arr[i][j];
if (i > 0)
sum[i][j] += sum[i - 1][j];
if (j > 0)
sum[i][j] += sum[i][j - 1];
if (i > 0 && j > 0)
sum[i][j] -= sum[i - 1][j - 1];
//System.out.print(sum[i][j] + " ");
}
//System.out.println();
}
for(int i=0;i<=n-m;i++)
for(int j=0;j<=n-m;j++){
int ss=sum[i+m][j+m]-sum[i][j+m]-sum[i+m][j]+sum[i][j];
if(ss>ans)
ans=ss;
}
System.out.println("#"+test_case+" "+ans);
}
}
}
Time Complexity: O(n²)