탭고리즘 2024-12-27 월간 판매 실적 구간 합 계산하기

 

• 문제설명
  1월부터 12월까지의 실적을 첫 줄에 정수로 입력받고 두 번째 줄에 질의의 개수를 입력받는다. 그 후 두 개의 달을 입력받는데 L월부터 R월까지의 총판매실적을 구하여 출력하면 된다. 

• 제출코드     

import java.util.Scanner;

public class SalesPrefixSum {

    // 누적합을 계산하는 메서드
    public static int[] calculatePrefixSums(int[] sales) {
        int[] prefixSums = new int[sales.length + 1]; // 누적합 배열 (0으로 초기화됨)
        for (int i = 1; i <= sales.length; i++) {
            prefixSums[i] = prefixSums[i - 1] + sales[i - 1]; // 현재까지의 합 계산
        }
        return prefixSums;
    }

    // 구간 합을 계산하는 메서드
    public static int querySum(int[] prefixSums, int l, int r) {
        return prefixSums[r] - prefixSums[l - 1]; // 구간 [l, r]의 합
    }

    // 메인 메서드
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        // 판매 데이터 입력
        int n = sc.nextInt(); // 판매 데이터의 개수
        int[] sales = new int[n];
        for (int i = 0; i < n; i++) {
            sales[i] = sc.nextInt(); // 판매 데이터 입력
        }

        // 누적합 계산
        int[] prefixSums = calculatePrefixSums(sales);

        // 쿼리 입력 및 처리
        int Q = sc.nextInt(); // 쿼리 개수
        for (int i = 0; i < Q; i++) {
            int L = sc.nextInt(); // 구간 시작 인덱스
            int R = sc.nextInt(); // 구간 끝 인덱스
            System.out.println(querySum(prefixSums, L, R)); // 구간 합 출력
        }

        sc.close(); // Scanner 닫기
    }
}

 

• 코드설명
  이 문제는 딱 보는 순간 누적합이 떠올랐다. 먼저 12개의 실적들을 sales배열에 담는다. 그러고 구간합을 계산해줄건데 만약 4월부터 7월까지의 실적을 구해야 한다면 7월까지의 총실적에서 3월까지의 총실적을 빼서 구할 수 있다.
  누적합을 구하기 위해서 prifixSums 배열을 만들고 0번째 인덱스가 아닌 1번째 인덱스부터 접근한다.

for (int i = 1; i <= sales.length; i++) {
            prefixSums[i] = prefixSums [i - 1] + sales [i - 1]; // 현재까지의 합 계산
        }

 

prefixSums[i]에는 i번재 달까지의 누적합을 저장해 둔다.

예를 들어 4월까지의 누적합에는 3월까지의 누적합과 4월의 실적을 더해서 저장하면 된다.

prefixSums에는 그전 달까지의 누적합이 들어가야 하므로 i-1번째 인덱스에 접근하고 sales에는 인덱스가 0부터 시작하므로 4월의 실적을 더하려면 세 번째 인덱스에 접근해야 한다. 그러므로 i-1번째 인덱스로 접근한다.

// 구간 합을 계산하는 메서드
    public static int querySum(int [] prefixSums, int l, int r) {
        return prefixSums [r] - prefixSums [l - 1]; // 구간 [l, r]의 합
    }

 

이제 l월부터 r월까지의 구간합을 구해야 한다. 
위에서 prefixSums에 누적합을 구해놨으니 이를 이용하면 된다.
이전에 말했듯이 4월부터 7월까지의 실적을 구하기 위해서는 7월까지의 누적 실적에서 3월까지의 누적 실적을 빼면 된다.
그러면 4, 5, 6, 7월까지의 실적을 더한 값만 남게 된다.
이를 코드로 나타내면 prefixSums [r] - prefixSums [l-1]로 나타낼 수 있다.