백준 2559번 수열 (C++)

문제

정답 코드

#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];
}

문제 풀이의 흐름

1. 각각의 상황마다 더해주는 방법은 비효율 적일 것이다.

2. 따라서 이미 이전에 계산한 값에서 하나씩 늘어날 때마다 제일 앞에 있는 원소를 빼고 다음 입력을 더해주는 방법을 사용을 한다.

3. 다 더해주면 sum배열에 원하는 결과값들이 들어있을 것이다.

4. 그 배열을 오름차순으로 정렬해준다

5. 시작할 때 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