📙[Algo] 24.01.26 알고리즘

알고리즘 문제) BOJ 11660. 구간 합 구하기 5

11660번: 구간 합 구하기 5

문제 요약

• N*N크기 표에서 (x1, y1)에서 (x2, y2)까지 합 구하기

• 여기서 (2,2) ~ (3,4)까지 합은 3 + 4 + 5 + 4 + 5 + 6 = 27

시간 제한

• 1초

입력

• 표의 크기 N, 합을 구해야 하는 횟수 M
  • 1≤N≤1024
  • 1≤M≤10만
• N개의 줄에 표에 채워진 숫자들이 주어짐
  • 1000이하 자연수
• M개의 줄에 네 개의 정수 x1, y1, x2, y2 주어짐
  • (x1 ≤ x2, y1 ≤ y2)

출력

• M줄에 (x1,y1)부터 (x2,y2)까지의 합 출력

접근법

• 쿼리가 10만 개가 주어지고, 표의 크기가 최대 1024이기 때문에 최악의 경우 10만 * 1024 * 1024의 연산이 필요할 것이다.
• 2차원 누적합 배열을 만든다.
  • arr[i][j] = arr[i-1][j] + arr[i][j-1] - arr[i-1][j-1] + arr[i][j]

코드

import java.io.*;
import java.util.*;

public class Main {
    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;

        st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

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

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

            sb.append(arr[x2][y2] - arr[x1 - 1][y2] - arr[x2][y1 - 1] + arr[x1 - 1][y1 - 1] + "\n");
        }


        bw.write(String.valueOf(sb));
        bw.flush();
        bw.close();
        br.close();
    }
}

 

알고리즘 문제) BOJ 1749. 점수따먹기

1749번: 점수따먹기

문제 요약

• N*M 행렬 → 각 칸에 -10,000 이상 10,000 이하의 정수 쓰기
• 부분 행렬 정수의 합 구하기 ⇒ 최대합 구하기

시간 제한

• 2초

입력

• N M
  • 1 < N < 200
  • 1 < M < 200
• N개의 줄에 행렬 원소가 주어짐 !!

출력

• 최대의 합을 출력

접근법

• 일단 2차원 구간합 배열로 만든다.
• 부분 행렬은 (1,1)부터 시작해서 (N,M)까지 구하는데, 이미 본 부분 행렬은 또 볼 필요가 없다.
  • 즉 현재 칸 기준 row, col 이상만 탐색한다.
    • 예를 들어, (3,3) 은 (3 ~ N, 3 ~ M)까지만 탐색한다.
• 즉, 시작 포인트 (x1, y1 ) 끝 포인트 (x2, y2)를 정해준다.
  • 2중 for문으로 일단 시작 포인트를 정해주고
    • 시작 포인트 포함 (x1 ~ N, y1 ~ M)까지 끝 포인트를 찾는다.
      • 끝 포인트를 찾으면 해당 부분 행렬의 합계를 구한다
      • arr[x2][y2] - arr[x1-1][y2] - arr[x2][y1-1] + arr[x1-1][y1-1]
    • 끝 포인트 지정할 때 어떻게 하지..? 그냥 2중 for문하면 시간초과 뜰텐데,,,,
      • 왜 안뜨지???

코드

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


public class Main {
    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;

        st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        int[][] arr = new int[N + 1][M + 1];
        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= M; j++) {
                arr[i][j] = arr[i - 1][j] + arr[i][j - 1] - arr[i - 1][j - 1] + Integer.parseInt(st.nextToken());
            }
        }

        int answer = Integer.MIN_VALUE;
        for (int x1 = 1; x1 <= N; x1++) {
            for (int y1 = 1; y1 <= M; y1++) {
                for (int x2 = x1; x2 <= N ; x2++) {
                    for (int y2 = y1; y2 <= M ; y2++) {
                        answer = Math.max(answer, arr[x2][y2] - arr[x1-1][y2] - arr[x2][y1-1] + arr[x1-1][y1-1]);
                    }
                }
            }
        }

        bw.write(String.valueOf(answer));
        bw.flush();
        bw.close();
        br.close();
    }
}