인프런 커뮤니티 질문&답변

#include <bits/stdc++.h>

using namespace std;

 

int n, k, temp, psum[100001], ret = -987654321;

 

int main(){

ios_base::sync_with_stdio(false);

cout.tie(0);

cin.tie(0);

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 <<endl;

return 0;

}

 

코드 전체를 가져 왔습니다.

i가 순회할 때, 1부터 시작하지만 그렇게 되면 psum[1] = psum[0] - temp가 되는데 이는 0번째가 초기화되지도 않았는데 참조하게 됩니다. 그렇다고 psum[0]이 0은 아니니까요.

 

그리고 

ret = max(ret, psum[i] - psum[i-k]); 에서 k가 5일 때, psum[5] - psum[0]가 되는데

psum[4]도 빼지 않고 후보군에 포함되어야 하는데 모든 범위를 순회했다고 볼 수 없습니다.

 

그래서 저는 treadmill 구조를 떠올려서 만들었습니다.

제가 지적한 오류가 맞는지 글을 남기는 겁니다.

 

#include <bits/stdc++.h>

using namespace std;

 

 

 

int main(){

ios_base::sync_with_stdio(false);

cout.tie(0);

cin.tie(0);

int n, k, tmp;

cin >> n >> k;

vector<int> v1(n,0);

for(int i=0;i<n;i++){

cin >> tmp;

v1[i]=tmp;

}

tmp =0;

for(int i=0;i<k;i++){

tmp += v1[i];

}

//미세섬유에서 treadmill model를 모사한 two pointer 

int tmp2= tmp;

for(int i=0;i<n-(k);i++){

tmp -= v1[i];

tmp += v1[i+k];

if(tmp2 < tmp) tmp2 =tmp;

}

 

cout << tmp2;

return 0;

}