백준6 [C++, Python] 투 포인터 3) BOJ 1806 부분합 https://www.acmicpc.net/problem/1806 1806번: 부분합 문제 10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 합이 특정값 S가 되는 부분 집합의 수를 구하는 문제에서 변형되어 합이 S이상인 부분 집합 중에 원소 개수가 가장 적은 부분집합의 원소 수를 구하는 문제이다. 만족하는 부분 집합이 없으면 0을 출력한다. 그래서 바뀐 부분이 1) start, end를 움직일때 cnt를 빼고 더해준다. 2) cnt >= mini 이면 start를 움직인다. (이전 문제에서는 sum >= S이면 이었음) 3) .. 2020. 8. 12. [C++, Python] 투 포인터 2) BOJ 1644 소수의 연속합 https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 문제 하나 이상의 연속된 소수의 합으로 나타낼 수 있는 자연수들이 있다. 몇 가지 자연수의 예를 들어 보면 다음과 같다. 3 : 3 (한 가지) 41 : 2+3+5+7+11+13 = 11+13+17 = 41 (세 가지) 53 : 5+7+11+13+17 = 53 (두 www.acmicpc.net 1. C++ #include #include using namespace std; int N; int ans = 0; bool primeArr[4000001]; vector prime; void Eratos(int n) { if (n 2020. 8. 12. 이전 1 2 다음 728x90 반응형