[1644] - 소수의 연속합

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

1644번: 소수의 연속합

접근 방식

시간초과를 염려해서 에라스토테네스의 체 또는 제곱을 이용해 소수를 빠르게 구하고, 투포인터를 사용해서 범위내의 소수를 더해주었다.

 

문제 풀이

• 주어진 n값 이하의 소수 구해서 리스트에 넣기 - 에라스토테네스의 체 또는 제곱을 이용해 빠르게 구하기
• start와 end 포인터를 2개 놓고 0으로 설정, start가 end와 작거나 같고, end가 리스트의 크기보다 작을 때 까지 while문
• start ~ end 사이의 값을 더한 후, 크면 start를 1올리고 작으면 end를 1 올리기 - 같으면 count와 end값 1올리기
• 반복문을 탈출하면 count값 출력

누적합을 썼으면 더 빠르게 구할 수 있을 것 같다.

using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

namespace Baekjoon.Gold
{
    class _1644
    {
        static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());
            List<int> list = new List<int>();

            //소수 구하기
            for(int i = 2; i<=n; i++)
            {
                bool isprime = true;
                for (int j = 2; j * j <= i; j++)
                {
                    if (i % j == 0)
                    {
                        isprime = false;
                        break;
                    }
                }
                if (isprime)
                    list.Add(i);
            }
            //Console.WriteLine(string.Join(" ", list));

            int count = 0;
            int start = 0;
            int end = 0;
            while(start <= end && end < list.Count)
            {
                int sum = 0;
                for (int i = start; i <= end; i++)
                    sum += list[i];

                if (sum > n)
                    start++;
                else if (sum < n)
                    end++;
                else
                {
                    end++;
                    count++;
                }
            }

            Console.WriteLine(count);
        }
    }
}