[백준/C++] 2559 수열

https://www.acmicpc.net/problem/2559

2559번: 수열

시간 복잡도를 잘 고려해야 하는 문제였다. 

1초정도가 나왔는데 

 

처음에는 문제를 보고 당연히 for 문 두번 돌렸다가 시간 초과가 떴다 ㅠ

 

 

[시간초과]

#include<bits/stdc++.h>
using namespace std;

int main() {
	int N, K;
	cin >> N >> K;
	vector<int> nums;
	for (int i = 0; i < N; i++) {
		int n;
		cin >> n;
		nums.push_back(n);
	}
	int max = 0;
	for (int i = 0; i < N - (K - 1); i++) {
		int sum = 0;
		for (int j = 0; j < K; j++) {
			sum += nums[i + j];
		}
		if (sum >= max) {
			max = sum;
		}
	}

	cout << max;


	return 0;
}

낄낄.. 바보녀석

 

풀고나서 알고리즘 분류를 보니까 

누적합은 그렇다치고 두 포인터랑 슬라이딩 윈도우는 대체 뭘까? 왜 이런 분류가 된거지?

 

풀이 방법은 다음과 같다 .

입력을 받을 때 덧셈까지 해결해야 하는데, 문제 조건이 "더하기" 이다. 

더한건 다시 빼버리면 되기 때문에

 

모두 더해서 필요한만큼을 빼주면 되는거다. 

 

입력값이 

3 -2 -4 -9 0 3 7 13 8 -3

위와 같으면, 입력을 받으면서 한 리스트에 모두 더한 값을 넣어준다. 

 

3 1 -3 -12 -12 -9 -2 11 19 16

그러면 위와 같이 되는데 

 

두개의 연속하는 숫자 중 최대값을 찾아야 한다면? K=2?

0번째 index는 포함하지 않아야 하고, 1번째 index부터 max값 비교를 시작해야한다. 

=> K-1번째 요소 부터 비교를 시작해야한다.

 

2번째 index인 -3의 경우엔

-3 = 3 + -2 + -4 의 수식을 가진다. 

-3 = 3 + -2 + -4 (-3) 를 하면,  1, 2 index의 합이 된다. 

 

즉 , 2번쨰 index의 값에서 0 번째 index의 값을 빼야하는 거니까. 

2-K => i번째 인덱스 - i-K번째 인덱스

가 된다. 

 

 

[정답]

#include<bits/stdc++.h>
using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	int N, K;
	cin >> N >> K;
	//vector<int> nums;
	int nums[100000];	

	for (int i = 0; i < N; i++) {
		int n;
		cin >> n;
		if (i == 0)nums[i] = n;
		else nums[i] = nums[i-1] + n;
	}

	int max = nums[K - 1];

	for (int i = K; i < N; i++) {
		if (max <= (nums[i] - nums[i - K])) {
			max = nums[i] - nums[i-K];
		}
	}

	cout << max;

	return 0;
}

 

 

 

[보완]

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

 

max()함수,

Python만큼 편리하진 못해서 배열을 넣으면 max를 뽑아주진 않더라. 

무조건 안에 들어가는 첫번째 인자와 두번째 인자만 비교한다.

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

   ret = max(ret, psum[i] - psum[i-];)

}

이걸로 하면 편하긴 하겠더라. 외워두장 ㅇㅅㅇ.. 근데 굳이 안외워도 if 써도 될거같기도 ?

나는 0번째 부터 했는데 1번째 비워두고 했어도 편했을거 같다 어차피 +0은 0이니까. 

 

 

[회고]

ios_base::sync_with_stdio(false);

cin.tie(NULL); cout.tie(NULL);

이게 속도를 조금 빠르게 해주는 코드로 알고 있는데, 잘 안쓰게 된다. 앞으로는 문제 풀 때마다 써야지 

 

사실 for문으로 돌렸을 때도 max = 0으로 시작한게 어차피 틀렸을 거 같긴 하다. 이런 사소한 부분을 신경써야 하는데 

그게 잘 안된다.

 

list 컨테이너랑 vector 컨테이너가 push_back 했을 때 시간 복잡도가 O(1) 이었던 거 같아서 썼는데 

vector 컨테이너는 O(n) 이었음 바보 ㅎ 

vector  컨테이너의 push_back은 O(1)이 맞다... 임의의 위치에 원소 추가 및 제거 v.insert(v.begin()+1, 100) 이 O(n)

 

list 컨테이너는 진짜 어떻게 쓰는건지 잘 모르겠더라 아무래도 C++ 포인터, 주소 같은걸 다시 공부할 필요가 매우매우매우 있을 듯.. => list는 index로 접근이 안됨.. 후..