![]()
문제 풀이 에라토스테네스의 체와 두 포인터 알고리즘을 사용한다. N까지 소수를 에라토스테네스의 체로 구한다. 가장 작은 소수인 2부터 두 포인터 알고리즘을 시작한다. (start, end = 2) start가 end 초과일 때까지 진행한다. start에서 end까지 소수의 합이 N이하라면 end를 다음 소수까지 증가시킨다. 초과라면 start를 다음 소수까지 증가시킨다. 코드 #include using namespace std; const int MAX = 4'000'001; bool prime[MAX]; // 에라토스테네스의 체 // N까지의 수 중 소수는 true로 표시 void eratosthenes(int N) { memset(prime, false, sizeof(prime)); for (int ..
![]()
문제 풀이 2중 for문을 사용하면 시간초과가 발생한다. 두 포인터 알고리즘을 사용한다. start에서 end 까지의 합이 S미만이라면 end를 증가한다. 수열의 길이를 늘린다. S이상이라면 start를 증가시켜서 수열의 길이를 줄인다. 코드 #include #include using namespace std; int num[100'002]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(nullptr); int N, S; int sum = 0; int answer = INT_MAX; cin >> N >> S; for (int i = 1; i > num[i]; } int start = 0; int end = 0; while (start
![]()
문제 풀이 2중 for문을 돌려서 정답을 찾으면 시간 초과가 발생한다. 두 포인터 알고리즘을 이용한다. 용액의 입력값이 오름차순으로 입력된다. 용액 vector의 양쪽에서 부터 start와 end로 시작하여 검사한다. start가 end의 값을 넘을 때까지 검사하며, start와 end의 합의 절댓값이 현재 answer보다 작다면 갱신한다. start와 end의 합의 부호에 따라 start와 end의 값을 증가하거나 감소시킨다. 코드 #include #include #include using namespace std; int main() { int N; vector v; vector answer; cin >> N; v.resize(N); answer.resize(2); for (int i = 0; i <..
