[백준] 11660 구간 합 구하기 5 파이썬, 자바 풀이

※ 사용언어 : 파이썬, 자바 ※

 

▼ 문제 링크 ▼

https://www.acmicpc.net/problem/11660

11660번: 구간 합 구하기 5

 

---

 

문제 접근

1) 다이나믹 프로그래밍 알고리즘을 이용해, (1,1)부터 시작해 각 구간의 누적 합을 구한다. 

EX) (1,1) ~ (3,4) 까지의 구간 누적합 구하기

(3,4) 까지의 누적합은 (1,1)~(3,3) 누적합과 (1,1)~(2,4)까지 누적합을 더하고 배열[3][4]을 더하면 된다. 하지만 (3,4) 까지의 누적합과 (2,4) 누적합 사이에는 공통적으로 (1,1)~(2,3) 까지의 누적합이 존재한다. 그래서 공통으로 존재하는 (2,3) 까지의 누적합을 빼준다.

결론적으로 (3,4) 까지 구간의 합은 (3,3)까지의 구간 합 + (2,4)까지의 구간 합 - (2,3)의 구간 합 + 배열[3][4] 값 을 통해 구할 수 있다.

즉, 구하고 싶은 구간이 (X, Y) 인 경우 dp[X][Y]=dp[X][Y-1]+dp[X-1][Y] - dp[X-1][Y-1] + array[X][Y] 라는 식을 도출 할 수 있다.

 

2) (1,1) 부터 모든 구간의 누적합이 있는 dp를 응용하여 특정 구간의 합을 구한다.

EX) (2,2) ~ (3,4) 까지의 구간 누적합을 구하고 싶은 경우

(2,2) ~ (3,4) 의 구간을 구하기 위해서는 (1,1) ~ (3,4) 까지의 구간합을 이용해야한다.

(1,1) ~ (3,4) 까지의 구간합에서 (1,1) ~ (3,1) 까지의 구간합과 (1,1) ~ (1,4) 까지의 구간합을 제거하면 (2,2) ~ (3,4) 의 구간 합을 구할 수 있다.  이때, (1,1) 구간이 (1,1) ~ (3,1) 까지의 구간합과 (1,1) ~ (1,4) 까지의 구간합에 중복으로 들어가 두 번 빠지게 됨으로 (1,1) 구간의 합을 한 번 더해준다.

결과적으로 (2,2) ~ (3,4) 의 구간의 합 = dp[3][4] - dp[3][1] - dp[1][4] + dp[1][1] 이다.

즉, 구하고 싶은 구간이 (x1,y1) ~ (x2,y2) 구간 합 = dp[x2][y2] - dp[x2][y1-1] - dp[x1-1][y2] + dp[x1-1][y1-1] 이다.

 

 

---

 

문제풀이 (With Python)

import sys

N,M=map(int,sys.stdin.readline().split())

number=[]
for i in range(N):
    number.append(list(map(int, sys.stdin.readline().split())))

dp=[[0 for _ in range(N+1)] for _ in range(N+1)]

for a in range(N):
    for b in range(N):
        dp[a+1][b+1]=(dp[a][b+1]+dp[a+1][b]-dp[a][b])+number[a][b]


for j in range(M):
    x1,y1,x2,y2=map(int,sys.stdin.readline().split())
    print(dp[x2][y2]-dp[x2][y1-1]-dp[x1-1][y2]+dp[x1-1][y1-1])

◇ number 배열이 0부터 시작하기 때문에 dp[X][Y]=dp[X][Y-1]+dp[X-1][Y] - dp[X-1][Y-1] + array[X][Y] 식에서 (X,Y)에 각각 (a+1,b+1)을 대입해서 식을 세운다. 

(dp 연산들만 따로 괄호로 묶은 것은 보기 편하려고 묶은 것뿐, 괄호를 쓰지 않아도 통과가 됩니다.)

 

 

---

 

 

문제풀이 (With JAVA)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st=new StringTokenizer(br.readLine());

        int N=Integer.parseInt(st.nextToken());
        int M=Integer.parseInt(st.nextToken());

        int[][] number=new int[N+2][N+2];
        for (int i = 1; i < N+1; i++) {
            StringTokenizer value=new StringTokenizer(br.readLine());
            for (int j = 1; j < N+1; j++) {
                number[i][j]=Integer.parseInt(value.nextToken());
            }
        }

        int[][] dp=new int[N+2][N+2];
        for (int a = 1; a < N+1; a++) {
            for (int b = 1; b < N+1; b++) {
                dp[a][b]=dp[a][b-1]+dp[a-1][b]-dp[a-1][b-1]+number[a][b];
            }
        }

        for (int z = 0; z < M; z++) {
            StringTokenizer position=new StringTokenizer(br.readLine());
            int x1=Integer.parseInt(position.nextToken());
            int y1=Integer.parseInt(position.nextToken());
            int x2=Integer.parseInt(position.nextToken());
            int y2=Integer.parseInt(position.nextToken());
            System.out.println(dp[x2][y2]-dp[x1-1][y2]-dp[x2][y1-1]+dp[x1-1][y1-1]);
        }
    }
}

◇ dp와 number 모두 1부터 시작되기 때문에 크기를 N+2로 설정했습니다.