[Java] 백준알고리즘 #2559 수열

백준알고리즘 #2559 수열

 

앞서 풀었던 누적합 문제와 유사한 문제이다.

2023.12.12 - [Java/백준알고리즘] - [Java] 백준알고리즘 #11659 구간 합 구하기 4

 

누적합 문제와 같이 배열에 누적합을 저장해주고

int n = sc.nextInt();
int k = sc.nextInt();

int[] temp = new int[n + 1];
temp[0] = 0;                                // 배열의 첫번째(0번째)는 0
for (int i = 1; i <= n; i++) {
    temp[i] = temp[i - 1] + sc.nextInt();   // 누적합
}

 

 

k만큼 구간의 합을 구해야 하므로 반복문 범위를 조절해서 구간합을 구하면 된다.

for (int i = k; i <= n; i++) {
    int sum = temp[i] - temp[i - k];        // 구간 합
    if (sum > max) {
        max = sum;
    }
}
System.out.println(max);

 

 

전체 코드는 다음과 같다.

// 해설참조 : sehyeok.tistory.com 

import java.io.IOException;
import java.util.Scanner;

public class Main {
    public static void main(String args[]) throws IOException {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();

        int[] temp = new int[n + 1];
        temp[0] = 0;                                // 배열의 첫번째(0번째)는 0
        for (int i = 1; i <= n; i++) {
            temp[i] = temp[i - 1] + sc.nextInt();   // 누적합
        }
        int max = temp[n];                          // 최대값

        for (int i = k; i <= n; i++) {
            int sum = temp[i] - temp[i - k];        // 구간 합
            if (sum > max) {
                max = sum;
            }
        }
        System.out.println(max);

        sc.close();
    }
}

 

 

 

..는 틀렸습니다 가 나온다.

 

왜냐하면 max값의 초기값이 temp[n] (마지막 누적합 값) 이면 될 것이라 생각했는데,

10 5

100 0 100 0 100 0 100 0 0 0 과 같은 경우

마지막 누적합 값이 400이고

구간별 최대값은 300이므로 에러가 발생하는 것.

따라서 그냥 int형의 최소값을 저장해주면 된다.

int max = Integer.MIN_VALUE;

 

전체 코드는 다음과 같다.

// 해설참조 : sehyeok.tistory.com 

import java.io.IOException;
import java.util.Scanner;

public class Main {
    public static void main(String args[]) throws IOException {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();

        int[] temp = new int[n + 1];
        temp[0] = 0;                                // 배열의 첫번째(0번째)는 0
        for (int i = 1; i <= n; i++) {
            temp[i] = temp[i - 1] + sc.nextInt();   // 누적합
        }
        int max = Integer.MIN_VALUE;                // 최대값

        for (int i = k; i <= n; i++) {
            int sum = temp[i] - temp[i - k];        // 구간 합
            if (sum > max) {
                max = sum;
            }
        }
        System.out.println(max);

        sc.close();
    }
}