문제
정답 코드
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
ios :: sync_with_stdio(0);
cin.tie(0);
int day;
int c_time;
cin >> day >> c_time;
vector<int> tp(day, -2147483647);
vector<int> sum(day, -2147483647);
for (int i=0 ;i < day;i++)
{
cin >> tp[i];
if (i == c_time -1)
{
sum[i] =0;
for (int j = 0; j < c_time; j++)
{
sum[i]+= tp[j];
}
}
else if (i >= c_time)
sum[i] = sum[i - 1] + tp[i] - tp[i-c_time];
// cout << sum[i] << " ";
}
sort(sum.begin(), sum.end(),greater<int>());
cout << sum[0];
}
문제 풀이의 흐름
- 각각의 상황마다 더해주는 방법은 비효율 적일 것이다.
- 따라서 이미 이전에 계산한 값에서 하나씩 늘어날 때마다 제일 앞에 있는 원소를 빼고 다음 입력을 더해주는 방법을 사용을 한다.
- 다 더해주면 sum배열에 원하는 결과값들이 들어있을 것이다.
- 그 배열을 오름차순으로 정렬해준다
- 시작할 때 int최소값으로 할 필요 없이 그냥 -101정도로 해주면 되는데 문제를 꼼꼼히 읽지 않아서 저렇게 초기화를 해줬다..
주의 할 점
문제 자체가 인덱스 계산과 부등호가 헷갈릴만 한 요소가 꽤나 들어있었다.
처음에는 모든 값을 더해서 누적합을 이용해서 풀었는데 정말 신기하게 예제 입력이 다 맞아서 그대로 제출했다가 하나씩 찍어보다가 논리 오류를 발견했다.
인덱스 값이 헷갈리면 일단 넣어보기보다는 직접 써가면서 연산을 하는 걸 추천한다.
반성 및 고찰
틀린코드
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
ios :: sync_with_stdio(0);
cin.tie(0);
int day;
int c_time;
cin >> day >> c_time;
vector<int> tp(day, 0);
vector<int> sum(day, 0);
for (int i=0 ;i < day;i++)
{
cin >> tp[i];
if (i == 0)
sum[i] = tp[i];
else if (i <= c_time)
sum[i] = sum[i - 1] + tp[i];
else
sum[i] = sum[i - 1] + tp[i] - tp[i - c_time];
}
sort(sum.begin(), sum.end(),greater<int>());
cout << sum[0];
}
문제를 제대로 읽지 않고 이렇게 하면 되지 않을까라고 생각을 하고 머리속으로 정립시키지 않고 무작정 코드를 완성해버렸다.
앞으로는 이런식으로 하지 않아야겠다.
또 이 문제는 왠지 더 어렵게 낼 수 있는 문제인데 입력을 하나 더 줘서 쉽게 만든 느낌도 받았다.
Uploaded by N2T