2559 수열 JAVA

 

나는 오늘 누적합을 오늘 처음 풀어봤는데 앞전 문제에서도 그렇고 알고리즘 능력이 올라갔다는 생각이 들었다,

내 생각에 누적합은 확실히 매우 효율적이라는거다.

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

 

package Algo.Queue;
import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class S2558 {
    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()), K = Integer.parseInt(st.nextToken());

        int[] numArr = new int[N], preFixSum = new int[N+1];

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

        int[] tmp = new int[N-K+1];

        int a = K, b = 1; // 임의의 값들

        for(int i = 0; i < N-K+1; i++) {
            tmp[i] = preFixSum[a++] - preFixSum[(b-1)];
            b++;
        }

        Arrays.sort(tmp);
        System.out.println(tmp[tmp.length-1]);
    }
}

 

위의 코드는 내가 작성한 코드이다. 나는 처음엔 누적합을 깨닫지 못해서 이중반복문을 통해서 풀고 제출했더니 

입력값이 너무 큰 나머지, 시간 초과가 떴다. 그래서 누적합을 구현했는데, 위와 같이 구현했다.

코드에 대해서 간략히 설명을 하고 싶다.

 

입력값을 받는 부분은 넘어가고, 누적합이란 모든 값들의 합을 누적하여 저장하는 형식이다.

따라서 어떤 범위의 값을 알고 싶으면 예를 들어 i~j의 범위를(i < j) 알고 싶을 때 arr[j] - arr[i-1]을 연산하면 된다. 

 

예를 들어서 1 2 3 4 5 6의 값을 누적합으로 받으면

0 1 3 6 10 15 21이 배열에 저장이 될 것이고, 숫자 1~4의 총합을 구하고 싶으면 

위의 공식 대로 index 4 = 10, index 1-1 = 0이므로 10 - 0 = 10이라는 결과가 나온다.
그럼 1+2+3+4 = 10이 성립이 되었다.

 

이 공식을 이용하면 입력값이 큰 경우도 이중반복문을 이용하지 않고 한개의 반복문으로도 원하는 값을 구할수 있다.

문제의 입력예시로 예를 들겠다.

 

수의 개수 10을 입력 받고, 연속된 날짜가 두 날인 경우, 2개씩의 범위를 계산하여야 한다.

그럼 규칙을 찾아보면 (1,2)(2,3)(3,4).... 을 끝까지 구해야 하고 

연속된 날짜가 다섯 날인 경우 (1,5)(2,6)(3,7)...이 될 것이다.

따라서 아래와 같이 구현할 수 있다.

 

int[] tmp = new int[N-K+1];

int a = K, b = 1; // 임의의 값들
for(int i = 0; i < N-K+1; i++) {
    tmp[i] = preFixSum[a++] - preFixSum[(b-1)];
    b++;
}