최대 매출 / 연속부분수열

최대 매출

✏️ 문제

* 설명
현수의 아빠는 제과점을 운영합니다. 현수 아빠는 현수에게 N일 동안의 매출기록을 주고 
연속된 K일 동안의 최대 매출액이 얼마인지 구하라고 했습니다.
만약 N=10이고 10일 간의 매출기록이 아래와 같습니다. 이때 K=3이면
12 1511 20 2510 20 19 13 15
연속된 3일간의 최대 매출액은 11+20+25=56만원입니다.
여러분이 현수를 도와주세요.

* 입력
첫 줄에 N(5<=N<=100,000)과 K(2<=K<=N)가 주어집니다.
두 번째 줄에 N개의 숫자열이 주어집니다. 각 숫자는 500이하의 음이 아닌 정수입니다.

* 출력
첫 줄에 최대 매출액을 출력합니다.

🔍풀이

첫 m개를 더한 window를 만들고, index대로 밀고나가며 n개만큼 확인한다. O(n)의 시간복잡도로 해결할 수 있다.

❗주의사항
반면 2중 for문을 돌아 각 index부터 k개의 항목을 계속 더하게 되면
O(n*k), 즉, 최대 O(100,000²)의 시간복잡도가 나오기 때문에 주의해야 한다.

 public int solution(int n, int m, int[] arr) {
        int answer = 0;
        int sum = 0;

        for(int i = 0; i < m; i++) {
            sum += arr[i]; // m = 5일 때  0~4까지
        }
        // 첫 window 완성
        answer = sum;
        for (int i = m; i < n; i++) {
            sum = sum - arr[i-m] + arr[i]; //
            answer = Math.max(answer, sum);
        }
        return answer;
}

연속부분수열

✏️ 문제

* 설명
N개의 수로 이루어진 수열이 주어집니다.
이 수열에서 연속부분수열의 합이 특정숫자 M이 되는 경우가 몇 번 있는지 구하는 프로그램을 작성하세요.
만약 N=8, M=6이고 수열이 다음과 같다면
1 2 1 3 1 1 1 2
합이 6이 되는 연속부분수열은 {2, 1, 3}, {1, 3, 1, 1}, {3, 1, 1, 1}로 총 3가지입니다.

* 입력
첫째 줄에 N(1≤N≤100,000), M(1≤M≤100,000,000)이 주어진다.
수열의 원소값은 1,000을 넘지 않는 자연수이다.

* 출력
첫째 줄에 경우의 수를 출력한다.

🔍풀이

❗주의사항