16. 최대 매출 (Sliding window)

 

# 풀이 1 => 시간초과

import java.util.*;

public class Main {

	public int solution(int n,int k,int []arr) {
		int max =0;
		
		for(int i=0;i<=n-k;i++) {
			int sum =0;
			for(int j=0;j<k;j++) {			
				sum += arr[i+j];
			}	
			if(sum>max) max = sum;			
		}
		return max;
	}

	public static void main(String[] args) {
		Main T = new Main();
		Scanner kb = new Scanner(System.in); 
		
		int n = kb.nextInt();
		int k = kb.nextInt();
		int []arr = new int[n];
		for(int i=0;i<n;i++) {
			arr[i] = kb.nextInt();
			
		}
		System.out.print(T.solution(n, k, arr));	
	}
}

 

 

# 풀이 2 => 슬라이딩 윈도우 방식 사용

 

 

- 처음에 k개 수의 합을 구한다.

- 그리고 그 박스를 끝까지 하나씩 옮겨가며 가장 큰 합을 찾는다.

- 하나씩 옮겨갈 때, 박스의 바로 다음수를 더하고, 박스의 처음 수를 빼는 방식을 사용한다.

 

import java.util.*;


public class Main {

	public int solution(int n,int k,int []arr) {

		int answer = 0;
		int sum = 0;
		
		for(int i=0;i<k;i++) sum += arr[i];
		answer = sum;
		for(int i=k;i<n;i++) {
			sum += (arr[i]-arr[i-k]);
			answer = Math.max(answer,sum);
		}
		return answer;
			
	}

	public static void main(String[] args) {
		Main T = new Main();
		Scanner kb = new Scanner(System.in); 
		
		int n = kb.nextInt();
		int k = kb.nextInt();
		int []arr = new int[n];
		for(int i=0;i<n;i++) {
			arr[i] = kb.nextInt();
			
		}
		System.out.print(T.solution(n, k, arr));	
	}
}