Beelog

www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 문제는 위와 같으며, 먼저 주어진 자연수보다 작거나 같은 소수를 모두 구해 배열로 저장한 뒤, low와 high 두개의 포인트를 만들어 앞에서부터 합을 구하면서 합이 n과 같아질 때 결과값을 하나 증가시키는 방식으로 문제를 해결하였습니다. 예제로 주어진 41을 기준으로 살펴보겠습니다. 41보다 작거나 같은 소수를 먼저 구해 배열로 저장합니다. 그런 다음, sum이 주어진 41보다 작은 경우 high를 한칸 뒤로 이동시키고 그 값을 sum에 추가해줍니다. 이렇게 같은 과정을 반복하다가 sum이 41과 같아진 경우, result의 값..

www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 문제는 위와 같으며, 정렬과 투 포인트를 사용하여 문제를 해결하였습니다. 먼저 주어진 용액들을 순서대로 정렬하였습니다. 그러고 난 뒤, low와 high 두 포인트를 생성하고 각각 주어진 용액 배열의 가장 앞과 뒤를 가리키도록 하였습니다. 그리고 이때 두 수의 합의 절댓값을 sum 변수에 저장하고 계산에 사용된 두 값을 result 배열에 저장하였습니다. 최종적으로 출력할 때 ..

www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 문제는 위와 같으며, 연속된 수들의 부분합 중에 주어지는 S 보다 큰 값을 이루는 수의 최소 개수를 구하는 문제였습니다. 처음에는 이 문제를 배열로 만들고 각 인덱스 개수만큼 수를 더해가면서 배열의 값을 뒤로 이동시키는 방식으로 풀었는데 시간 초과가 발생하였습니다...ㅠㅠ 그래서 이 문제를 low, high 두개의 인덱스 값을 포인트로 두어 두 값을 이동시키는 방식으로 해결하였습니다. 두 포인터를..