[BOJ][JAVA] 2559번: 수열, 1912번: 연속합, 2304번: 창고 다각형 - 누적합

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

---

오답노트(푸는 동안 사고과정 및 개선점)

누적합 문제다. 

처음에 고려안한 부분은 누적합 배열 시작 인덱스 부분이다.

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
    static int n, gap;

    public static void main(String[] args) throws Exception {
        //System.setIn(new FileInputStream("res/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        gap = Integer.parseInt(st.nextToken());
        int[] in = new int[n];
        int[] prefix = new int[n];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            in[i] = Integer.parseInt(st.nextToken());
            if (i == 0) {
                prefix[i] = in[i];
            } else {
                // 누적합
                prefix[i] = prefix[i - 1] + in[i];
            }
        }
        PriorityQueue<Integer> pq = new PriorityQueue<>((o1, o2) -> {
            return o2 - o1;
        });
        //이제 각 간격의 합을 pq에 넣기
        int idx = n - 1;
        while (true) {
            if (idx - gap < 0) break;
//            System.out.println(prefix[idx] + ", " + prefix[idx - gap]);
            pq.add(prefix[idx] - prefix[idx - gap]);
            idx--;
        }

        System.out.println(pq.poll());
    }
}

이렇게 해버리면 무슨 문제가 생기냐면 

10 3
100 -1 -1 -1 -1 -1 -1 -1 -1 -1

이 입력이 들어올 때 누적합 배열에는 다 들어가지만, 간격을 더할 때 98이 최대값이 아니라 3이 최대값이 나와버린다.

[100, 99, 98, 97, 96, 95, 94, 93, 92, 91]

이게 size가 n인 prefix인데, 내 로직 상 `n`번째 - `n-k`번째 누적합 항목을 빼면 그 사이의 누적합이 나오도록 되어있다. 이 경우 -3이 나오게 되고, 원래라면 100, -1, -1 이 세 수의 합이 98인데, 시작 항목을 간격으로 잡고 가버린 셈이 돼서 -3이 나오게 됐다. 그래서 시작 부분을 고려하게 되면 n+1 크기를 가진 prefix 배열을 만들어야 하고, 아래와 같이 누적합 배열이 구성된다.

prefix 배열 구성할 때는 그래서 1칸 더 크게 하는게 좋을 것 같다. DP랑 거의 동일한 개념으로 이해했다.

[0, 100, 99, 98, 97, 96, 95, 94, 93, 92, 91]

 

비슷한 문제로 연속합이 있다.

몇 번 연속해도 좋으니까 연속한 합이 가장 큰 수를 구하는 문제다.

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

여기서 떠올린 아이디어는 어차피 누적해서 합하는데, 값이 작아지는 경우에는 더하지 않고 가겠다는 것이다.

for (int i = 0; i < n; i++) {
    in[i] = Integer.parseInt(st.nextToken());
}
PriorityQueue<Integer> pq = new PriorityQueue<>((o1, o2) -> {
    return o2 - o1;
});
for (int i = 1; i <= n; i++) {
    prefix[i] = Math.max(prefix[i-1]+in[i-1], in[i-1]);
    pq.add(prefix[i]);
}

이러면 값이 주어진 입력 배열보다 작은 누적합 위치가 발생하면, 누적합 값에 이전 연속합을 무시하고, 새로 시작한다.

일종의 DP라고 볼수도 있지않을까?

 

좀 더 난이도있는 문제를 살펴보기 위해 누적합을 2번쓰는 문제를 풀어봤다.

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

문제를 잘 읽어야한다. 선분 시작점을 주는 것이 핵심이다.

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws Exception {
        // System.setIn(new FileInputStream("res/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int n = Integer.parseInt(st.nextToken());
        int maxH = -1;
        int maxIdx = -1;
        int[] input = new int[10001];

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int idx = Integer.parseInt(st.nextToken()); // 기둥 왼쪽면의 위치
            int h = Integer.parseInt(st.nextToken());
            input[idx + 1] = h; // idx 자체는 0이 없으나, 0-1 ,1-2 이렇게 간격으로 들어감 -> 정확히는 왼쪽 모서리 기준이니까 하나씩 밀기
            maxIdx = Math.max(idx, maxIdx);
            maxH = Math.max(h, maxH);
        }


        int[] pref = new int[maxIdx + 2]; // 앞뒤에 한칸씩 추가하기
        int[] suff = new int[maxIdx + 2]; // 앞뒤에 한칸씩 추가하기
        int[] maxPoint = new int[2]; //
        Arrays.fill(maxPoint, -1);
        int prev = 0;
        int prefSum = -1;
        int suffSum = -1;
        // l to r
        for (int i = 1; i <= maxIdx + 1; i++) {
            prev = Math.max(input[i], prev);
            pref[i] = pref[i - 1] + prev;
            if (input[i] == maxH) {
                maxPoint[0] = i;
                break;
            }
        }
        prev = 0;
        for (int i = maxIdx + 1; i >= 0; i--) {
            prev = Math.max(input[i], prev);
            suff[i - 1] = suff[i] + prev;
            if (input[i] == maxH) {
                maxPoint[1] = i;
                break;
            }
        }
        // max까지 합
        int maxLToR = -1;
        int maxRToL = -1;
        for (int i = 0; i < maxPoint[0]; i++) {
            maxLToR = Math.max(maxLToR, pref[i]);
        }
        for (int i = maxIdx + 1; i >= maxPoint[1]; i--) {
            maxRToL = Math.max(maxRToL, suff[i]);
        }
//        System.out.println(maxLToR + ", " + maxRToL);

        // 합치기

        int maxWidth = maxPoint[1] - maxPoint[0] + 1;

//
//        System.out.println(Arrays.toString(pref) + ", " + maxPoint[0] + ", " + maxH);
//        System.out.println(Arrays.toString(suff) + ", " + maxPoint[1] + ", " + maxH);
        System.out.println(maxLToR + maxRToL + maxWidth * maxH);
    }
}

완전히 같은 방식으로 아래 문제도 풀수있다.

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

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws Exception {
        System.setIn(new FileInputStream("res/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int H = Integer.parseInt(st.nextToken());
        int W = Integer.parseInt(st.nextToken());

        int[] heights = new int[W];
        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < W; i++) {
            heights[i] = Integer.parseInt(st.nextToken());
        }

        int[] leftMax = new int[W]; // 얘네가 창고다각형에 있던 prefix, suffix 역할
        int[] rightMax = new int[W];

        // 왼쪽에서 본 최대 높이 계산
        leftMax[0] = heights[0];
        for (int i = 1; i < W; i++) {
            leftMax[i] = Math.max(leftMax[i - 1], heights[i]);
        }

        // 오른쪽에서 본 최대 높이 계산
        rightMax[W - 1] = heights[W - 1];
        for (int i = W - 2; i >= 0; i--) {
            rightMax[i] = Math.max(rightMax[i + 1], heights[i]);
        }

        // 빗물이 고일 수 있는 양 계산
        int water = 0;
        for (int i = 0; i < W; i++) {
            int minHeight = Math.min(leftMax[i], rightMax[i]);
            if (minHeight > heights[i]) {
                water += minHeight - heights[i];
            }
        }

        System.out.println(water);
    }
}

---

정답코드

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
    static int n, gap;

    public static void main(String[] args) throws Exception {
        System.setIn(new FileInputStream("res/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        gap = Integer.parseInt(st.nextToken());
        int[] in = new int[n];
        int[] prefix = new int[n+1];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            in[i] = Integer.parseInt(st.nextToken());
            prefix[i+1] = prefix[i] + in[i];
        }
        System.out.println(Arrays.toString(prefix));

        PriorityQueue<Integer> pq = new PriorityQueue<>((o1, o2) -> {
            return o2 - o1;
        });
        //이제 각 간격의 합을 pq에 넣기
        int idx = n;
        while (true) {
            if (idx - gap < 0) break;
            pq.add(prefix[idx] - prefix[idx - gap]);
            idx--;
        }

        System.out.println(pq.poll());
    }
}

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
    static int n;

    public static void main(String[] args) throws Exception {
        // System.setIn(new FileInputStream("res/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        int[] in = new int[n];
        int[] prefix = new int[n + 1];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            in[i] = Integer.parseInt(st.nextToken());
        }
        PriorityQueue<Integer> pq = new PriorityQueue<>((o1, o2) -> {
            return o2 - o1;
        });
        for (int i = 1; i <= n; i++) {
            prefix[i] = Math.max(prefix[i-1]+in[i-1], in[i-1]);
            pq.add(prefix[i]);
        }
//        System.out.println(Arrays.toString(prefix));
        
        System.out.println(pq.poll());
    }
}

도움이 됐다면 댓글이나 공감 버튼 한 번씩 누르고 가주세요!