[백준] no11660: 구간 합 구하기5

문제

/**
 * 주어진 N * N 사이즈의 매트릭스에서
 * x1, y1 ~ x2, y2에 해당하는 숫자의 합을 구하시오
 */

문제 링크 : https://www.acmicpc.net/problem/11660

---

원리

* 1. DP 
* 2. 누적 합

---

풀이방법

1. 누적 합 중, 2차원 배열을 이용한 이중반복을 피하기 위한 방법 (예시)

: 매트릭스(이중배열)로 되어있는 수를 1차원 배열에 나열 한 뒤, 각 숫자는 N으로 나눈 나머지의 비교를 이용한 조건문으로 대체가 가능하다.

private static void calculate () {
       DP = new int[N*N+1];
       int num = (N*(y1-1))+x1;
       int finish = (N*(y2-1))+x2;
       int last = 0;

       while(num<=finish) {
            if(num%N>x2) {
                num += ((N-x2)+x1);
            } else if (num%N == 0 && x2!=N) { // x2와 N이 같은 경우의 엣지케이스
                num += x1;
            }else {
                DP[num] = DP[last] + arr[num];
                last = num;
                num++;
            }
       }
   }

예시

//        // 1 2 3 4 2 3 4 5 3  4  5  6  4  5  6  7
//        // 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

 

2. DP를 이용한 방법 : 이 문제의 경우, N이 1024까지 가능하고, 총 10000번의 반복이 이루어질 수 있어야 하므로, 누적 합 방식을 사용하면 시간초과가 발생한다.

 

---

나의 코드

1차 시도 : 누적 합 [백준 실패 - 범위 오류?]

import java.io.*;
import java.math.BigInteger;
import java.util.StringTokenizer;

public class no11660 {
    private static int N, M, x1, x2, y1, y2;
    private static int[][] matrix;
//    private static int[] arr;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        // 입력 구간
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        // 이중배열로 구하는 방식
        matrix = new int[N][N];

        for (int i = 0; i < N; i++) {
            StringTokenizer st2 = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < N; j++) {
                matrix[i][j] = Integer.parseInt(st2.nextToken());
            }
        }


        for (int i = 0; i < M; i++) {
            StringTokenizer st2 = new StringTokenizer(br.readLine(), " ");
            x1 = Integer.parseInt(st2.nextToken());
            y1 = Integer.parseInt(st2.nextToken());
            x2 = Integer.parseInt(st2.nextToken());
            y2 = Integer.parseInt(st2.nextToken());

            bw.write(""+calculate()+"\n");
        }

        bw.close();
    }
    private static int calculate () {
        int sum = 0;
        for (int y = y1; y <= y2; y++) {
            for (int x = x1; x <= x2; x++) {
                if(x>=x1) sum += matrix[y-1][x-1];
            }
        }
        return sum;
    }
}

 

2차 시도 : 누적 합 DP처럼 풀어보려 했으나, 결국 누적 합 방식이 되어버렸다. 따라서 백준 안에서 시간초과가 발생한다.

다만, 이중반복을 1중반복으로 바꿨음에도 1024 * 1024 * 10000이라는 범위가 커서 시간초과가 발생한다. 

    private static int N, M, x1, x2, y1, y2;
    private static int[] arr;
    private static int[] DP;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        // 입력 구간
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

    // 구간합
       arr = new int [N*N+1]; // 매트릭스를 1차원 배열로 나열
       int num = 0;
       for (int y = 0; y < N ; y++) {
           StringTokenizer st2 = new StringTokenizer(br.readLine(), " ");
           for (int x = 0 ; x < N ; x++) {
               num += 1;
               arr[num] = Integer.parseInt(st2.nextToken());
           }
       }

       /**
        * 조건문으로 반복
        */
       for (int i=0 ; i<M ; i++) {
           StringTokenizer st3 = new StringTokenizer(br.readLine(), " ");
           x1 = Integer.parseInt(st3.nextToken());
           y1 = Integer.parseInt(st3.nextToken());
           x2 = Integer.parseInt(st3.nextToken());
           y2 = Integer.parseInt(st3.nextToken());
           calculate();    
           bw.write(""+DP[(y2-1)*N+x2]+"\n");
       }

       bw.close();
   }


    // 1  2  3  4  2  3  4  5  3  4  5  6  4  5  6  7
    // 1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16
   private static void calculate () {
       DP = new int[N*N+1];
       int num = (N*(y1-1))+x1;
       int finish = (N*(y2-1))+x2;
       int last = 0;

       while(num<=finish) {
            if(num%N>x2) {
                num += ((N-x2)+x1);
            } else if (num%N == 0 && x2!=N) { // x2와 N이 같은 경우의 엣지케이스
                num += x1;
            }else {
                DP[num] = DP[last] + arr[num];
                last = num;
                num++;
            }
       }
   }

---

레퍼런스 코드

레퍼런스 링크의 설명이 매우 잘 되어있다. 두고두고 참고할 만한 링크.

참고링크 : https://subbak2.tistory.com/65