https://www.acmicpc.net/problem/2003 2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net 이전에 올렸던 [소수의 연속합]이라는 문제에서 투 포인터를 구현했을 때 if문과 break을 남발한 것이 마음에 걸려 같은 알고리즘의 문제를 풀어보았다. 골자는 똑같다. 구간합이 주어진 수 M과 같거나 큰 경우에는 start를 1 올리고, M보다 작은 경우에는 end를 1 올려 주어서 해당하는 arr의 값을 더해준다. M과 같은 경우에는 count도 1 더..
투포인터
1644번 : 소수의 연속합 https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 문제를 풀면서 필요했던 것은 1. 에라토스테네스의 체 2. 투 포인터 의 개념이었다. 1. 에라토스테네스의 체 숫자를 더하고 빼가면서 그 때마다 소수인지를 가늠하는 것은 비효율적이기 때문에, 자연수 N의 최대값인 4,000,000까지의 배열을 만들고, 각 숫자가 소수인지 먼저 찾았다. 소수란, 1과 자신 외에 약수가 없는 수를 말한다. 1) 그럼 가장 먼저 떠오르는 것은 2부터 4,000,000까지 for문을 돌리면서 자신보다 큰 수 중 자신으로 나눠지는 수가 있는지 확인하는 것이다. 하..
