BOJ 1644 소수의 연속합

2020. 9. 23. 22:48·알고리즘/BOJ

www.acmicpc.net/problem/1644

 

1644번: 소수의 연속합

첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000)

www.acmicpc.net

두 포인터를 활용한 재미있는 문제였다.

n을 입력받아서 소수 판정을 해주고 prime 배열에 넣어주고 두 포인터를 쓰면 된다.

 

#include <iostream>
#include <vector>
using namespace std;

const int MX = 4000001;
vector<bool> sieve;
vector<int> prime;
int s, e, sum, cnt;

void era(int n) {
	sieve.resize(n + 1, true);

	sieve[0] = sieve[1] = false;
	for (int i = 2; i * i <= n; i++) {
		if (sieve[i]) {
			for (int j = i * 2; j <= n; j += i) sieve[j] = false;
		}
	}
	for (int i = 2; i <= n; i++) {
		if (sieve[i]) prime.push_back(i);
	}
}

int main() {
	int n;
	cin >> n;

	era(n);
	while (1) {
		if (sum >= n) sum -= prime[s++];
		else if (e == prime.size()) break;
		else sum += prime[e++];
		if (sum == n) cnt++;
	}
	cout << cnt << endl;

	return 0;
}

 

주의해야 할 점은 배열의 인덱스를 잘못 건드리는 것이다. 

문제에서 소수 배열의 크기를 n까지만 잡아서 1시간은 고생한 것 같다.

'알고리즘 > BOJ' 카테고리의 다른 글

BOJ 2437 저울  (0) 2020.10.02
BOJ 6603 로또  (0) 2020.09.29
BOJ 2096 내려가기  (0) 2020.09.23
BOJ 2015 수들의 합 4  (0) 2020.09.23
BOJ 팰린드롬?  (0) 2020.09.22
'알고리즘/BOJ' 카테고리의 다른 글
  • BOJ 2437 저울
  • BOJ 6603 로또
  • BOJ 2096 내려가기
  • BOJ 2015 수들의 합 4
khyu2
khyu2
  • khyu2
    dev log
    khyu2
  • 전체
    오늘
    어제
    • 분류 전체보기
      • 알고리즘
        • BOJ
        • Programmers
        • Algorithm
        • SWEA
      • 개발
  • 블로그 메뉴

    • 홈
    • 태그
    • 방명록
  • 링크

  • 공지사항

  • 인기 글

  • 태그

    냅색
    피보나치 수
    이분탐색
    완전탐색
    팰린드롬
    BFS
    크루스칼
    분할 정복
    알고리즘
    행렬 제곱
    유니온 파인드
    구현
    우선순위 큐
    완전 탐색
    SWEA
    BOJ
    소수
    MST
    GREEDY
    이분 탐색
    dp
    다익스트라
    피사노 주기
    코딩테스트 연습
    조합
    dfs
    시뮬레이션
    큐
    트리
    프로그래머스
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.3
khyu2
BOJ 1644 소수의 연속합
상단으로

티스토리툴바