2559 수열

문제 포인트

누적합

 

해설 코드와 내 코드 비교

해설 코드는 최솟값을 고려하여 최댓값 비교

=> 최댓값을 구하라 -> 최솟값부터 최댓값 , 최솟값을 구하라 -> 최댓값부터 최솟값

해설 코드는 누적합(prefix sum)을 저장한 배열을 이용하여 구간합을 구함

=> K가 바뀔 때마다 입력값 배열을 다시 순회하여 구할 필요가 없음

내 코드는 슬라이딩 알고리즘을 이용하여 구간합을 구함

 

해설 코드

#include<bits/stdc++.h> 
using namespace std;  
typedef long long ll;  
int n, k, temp, psum[100001], ret = -1000000; 
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);cout.tie(NULL);
	cin >> n >> k; 
	for(int i = 1; i <= n; i++){
		cin >> temp; psum[i] = psum[i - 1] + temp; 
	} 
	for(int i = k; i <= n; i++){
		ret = max(ret, psum[i] - psum[i - k]);
	}
	cout << ret << "\n";
    return 0;
}

내 코드 1차

개선 필요

// 연속 K개 합 중 가장 큰 값
// 슬라이딩 

#include <iostream>
using namespace std;
int temper[100005];
int ret, mx;
int main(){
    int n, k;
    cin >> n >> k;
    for(int i = 0; i < n; i++) {
        cin >> temper[i];
        if(i < k)
            ret +=temper[i];
        
    }
    mx = ret;
    for(int i = k; i < n; i++){
        if(mx < ret + temper[i]-temper[i-k])
            mx = ret + temper[i]-temper[i-k];
        ret+=temper[i]-temper[i-k];
    }
    cout << mx << endl;
}

 

내 코드 2차

잘한점

- typedef 로 타입명 간소화

- max 라이브러리 사용하여 코드 간소화 (별도 라이브러리 import 필요 없음)

개선점

- 변수 네이밍: 구간합(Prefix sum) 배열 이름 ->psum

#include <iostream>
typedef long long ll;
using namespace std;

ll t[100005];
ll mx = -10000005;
int main(){
    int n, k, temp;
    cin >> n >> k;
    for(int i = 1; i <= n; i++){
        cin >> temp;
        t[i] = t[i-1] + temp;
    }
    for(int i = k; i <= n; i++){
        mx = max(mx, t[i] - t[i-k]);
    }
    cout << mx << endl;
}