문제
현수의 아빠는 제과점을 운영합니다. 현수 아빠는 현수에게 N일 동안의 매출기록을 주고 연속 된 K일 동안의 최대 매출액이 얼마인지 구하라고 했습니다.
만약 N=10이고 10일 간의 매출기록이 아래와 같습니다. 이때 K=3이면
12 15 11 20 25 10 20 19 13 15
연속된 3일간의 최대 매출액은 11+20+25=56만원입니다. 여러분이 현수를 도와주세요.
[입력설명]
첫 줄에 N(5<=N<=100,000)과 M(2<=K<=N)가 주어집니다.
두 번째 줄에 N개의 숫자열이 주어집니다. 각 숫자는 500이하의 음이 아닌 정수입니다.
[출력설명]
첫 줄에 최대 매출액을 출력합니다.
입력예제 1
10 3
12 15 11 20 25 10 20 19 13 15
출력예제 1
56
문제 풀이
예습 이론
슬라이딩 윈도우는 창문을 왼쪽으로부터 오른쪽으로 한칸씩 옮기는 작업을 한다. 합을 구할 때는, 이전 결과를 사용한다. 예를 들어, 4+7+10을 구하기 위해서는 이전 결과인 (2+4+7)에서 +10-2를 하면 된다.
코드
이 문제는 슬라이딩 윈도우를 활용한 문제다. 슬라이딩 윈도우의 개념은 위를 참고하자!개념만 알면 풀 수 있는 쉬운 문제이다.
<html>
<head>
<meta charset="UTF-8">
<title>출력결과</title>
</head>
<body>
<script>
function solution(k, arr){
let answer, sum=0;
for(let i=0; i<k; i++) sum+=arr[i];
answer=sum;
for(let i=k; i<arr.length; i++){
sum+=(arr[i]-arr[i-k]);
answer=Math.max(answer, sum); //answer, sum중 더 큰값을 answer에 대입
}
return answer;
}
let a=[12, 15, 11, 20, 25, 10, 20, 19, 13, 15];
console.log(solution(3, a));
</script>
</body>
</html>
내가 짱이다 😎 매일 조금씩 성장하기🌱
2개의 댓글
2021년 9월 13일
9/13 0~2인덱스까지 구한 후, answer=sum 해주기 (answer=MIN_SAFE_INTEGER도 문제에 답을 구하는데는 관계없지만, 논리에 따라 풀면 첫 m개의 합을 answer에 대입해주자)
답글 달기
9/12