https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 소수 판별 알고리즘 + 투포인터 알고리즘의 조합이다. 우선, 에라토스테네스의 체를 이용하여 소수를 걸러준다. N의 범위가 4백만이므로 그냥 이중 for문을 사용하면 TLE다. (소수를 거른다는 것은, 소수끼리만 따로 모아준다는 것을 뜻한다. 그렇게 된다면 자연스레 소수들은 연속되게 된다.) 거른 소수를 따로 저장해준 뒤, 이를 이용해 투포인터 알고리즘을 작동시킬 것이다. 필요한 변수들을 선언 해준 뒤, left와 right 사이의 구간합을 구해준다. 이때 구간합이 n보다 작으면 right가 가리키는 소수를 더해준다...
https://www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net N이 최대 100,000까지 입력이다. 하나하나씩 다 계산해가며 비교하면 100,000 x 100,000으로 1초안에 절대 풀 수 없게 된다. 그래서 이 문제는 이분탐색의 개념과 투 포인터를 활용한다. 우선, 배열을 쭉 오름차순으로 정렬한 뒤 (오름차순으로 정렬하면 음수는 절댓값이 큰 것이 앞에 오고, 양수는 절댓값이 큰 것이 뒤로 간다.) 두 개를 더 했을 때 ..
https://www.acmicpc.net/problem/14465 14465번: 소가 길을 건너간 이유 5 첫 줄에 N, K, B (1 ≤ B,K ≤ N)가 주어진다. 그 다음 B줄에는 고장난 신호등의 번호가 하나씩 주어진다. www.acmicpc.net 내가 푼 코드 #include #include #include using namespace std; int n, k, b; int cnt,num; bool arr[100001]; bool cmp[100001]; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> k >> b; for (int i = 0; i > num; //arr[i..
