(백준 1644번 소수의 연속합) 라이님 블로그 대회 알고리즘 따라잡기 14) 투 포인터, 슬라이딩 윈도우

https://blog.naver.com/PostView.naver?blogId=kks227&logNo=220795165570&parentCategoryNo=&categoryNo=299&viewDate=&isShowPopularPosts=false&from=postList

투 포인터(Two Pointers Algorithm), 슬라이딩 윈도우(Sliding Window) (수정: 2019-09-09)

DP2를 이해하다가 두통이 와서 나름 익숙한 투포인터와 슬라이딩 윈도우 파트를 먼저 보았다.

 

늘 그렇듯 설명은 라이님 블로그를 참고하면 된다!

 

이 문제는 다 풀고 메모리 사용량과 시간이 4년 전 문제풀이보다 너무 별로라서 다시 풀어본 문제@_@!

우선 첫번째 풀이는 아래 첨부해두었다.

 

그리고 몇가지를 손 보았는데

1. 에라토스테네스의 체 알고리즘 수정

https://blog.naver.com/PostView.naver?blogId=kks227&logNo=220793360258&parentCategoryNo=&categoryNo=299&viewDate=&isShowPopularPosts=false&from=postList

에라토스테네스의 체(Sieve of Eratosthenes) (수정: 2019-08-17)

이건 라이님의 알고리즘을 참고했다.

 

짝수 부분을 미리 처리해주면 실행 속도에서 약간의 이득을 얻을 수 있다! 그렇게 풀면 시간복잡도도 O(nlnlnN)!!!

N = 10^6 정도도 도전할만하다!

 

2. 라이님의 알고리즘을 그대로 차용하다가 생긴 문제

i를 int라고 정의했다고해서 i * i 역시 int라는 보장이 없다!!!!

 

그래서 이 부분을 확인할 때 (long long) i*i라고 해야 overflow가 안 생긴다^__^

 

3. 소수인지 아닌지 여부만 확인하려면 int가 아닌 bool로 저장하기!

메모리가 2만KB차이 난다 ㄷㄷ(2만KB = 2만 * 1024 Byte =  2만 * 1024 / 4 = 512만개의 int)

 

// 처음 맞은 코드
#include <iostream>
#include <vector>
using namespace std;

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

	int N; cin >> N;
	vector<int> v;
	vector<int> prime;
	v.resize(N+1); fill(v.begin(), v.end(), 1);
	v[0] = 0; v[1] = 0;

	int sum = 0; int j = 2;
	for (int i = 2; i < N+1; i++) {
		if (v[i] == 1) {
			prime.push_back(i);
			while (i * j <= N) {
				v[i * j] = 0;
				j++;
			}
			j = 2;
		}
	}

	int s = 0, e = 0, result = 0; long long total = 0;
	while(1) {
		if (total >= N) total -= prime[s++];
		else if (e == prime.size()) break;
		else total += prime[e++];
		if (total == N) result++;
	}

	cout << result;
	return 0;
}

// 개선한 코드
#include <iostream>
#include <vector>
using namespace std;

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

	int N; cin >> N;

	vector<bool> v;
	vector<int> prime;
	v.resize(N + 1, 1);
	v[0] = v[1] = 0; 

	prime.push_back(2);
	for (int i = 4; i <= N; i += 2) v[i] = 0;
	for (int i = 3; i <= N; i += 2) {
		if (v[i] == 1) {
			prime.push_back(i);
			if ((long long)i * i <= N) {
				for (long long j = i * i; j <= N; j += i * 2) {
					v[j] = 0;
				}
			}
		}
	}

	int s = 0, e = 0, result = 0; long long total = 0;
	while (1) {
		if (total >= N) total -= prime[s++];
		else if (e == prime.size()) break;
		else total += prime[e++];
		if (total == N) result++;
	}

	cout << result;
	return 0;
}

 

여튼여튼 주말에도 하나 풀어서 좀 뿌듯하다! 열공열공!