https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 생각 일단 숫자를 입력받으면 숫자보다 작은 수들 중에 소수인 것들을 모아서 배열에 집어넣어야 한다. 그리고 투 포인터를 활용하여 그 배열 안에서 n과 같은 연속합이 있는지 찾아보면 된다. 소수를 찾는 방법은 에라토스테네스의 체를 활용하면 된다. https://danidani-de.tistory.com/50 에라토스테네스의 체(소수 찾기) C++ / 과정 / 시간복잡도 :: DANIDANI 알고리즘 개념 고대 그리스 수학자 에라토스테네스가 만들어 낸 방법으로, 마치 체로 치듯이 수를 걸러낸다고 하여 '에라토스테네스의 ..
생각 투 포인터를 사용해서 풀 수 있다. st, en 두 포인터를 둔다. 1. 수들을 입력받아 배열에 저장한다. 2. 수의 합을 저장하는 변수 total은 arr[0]을 더 해주고, 줄의 길이를 저장하는 변수 len은 최대한 큰 수로 둔다(0x7fffffff). 3. en을 0으로 둔다. 4. en이 n보다 작고 total이 s보다 작다면 en을 한 칸 오른쪽으로 옮긴다. 5. 그러고도 en이 n보다 작다면 total에 arr[en]을 더 해준다. 6. 계속 더하다보면 total이 s보다 커진다. 7. 그러면 그 때 en-st+1이 len보다 작다면 len에 en-st+1을 저장한다. 8. st가 다음 칸으로 넘어가기 전에 total에서 arr[st]를 빼준다. 9. 만약 s보다 큰 부분합을 찾지 못했다..
https://www.acmicpc.net/problem/2230 2230번: 수 고르기 N개의 정수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에서 두 수를 골랐을 때(같은 수일 수도 있다), 그 차이가 M 이상이면서 제일 작은 경우를 구하는 프로그램을 작성하시오. 예를 들어 www.acmicpc.net 생각 투 포인터를 사용하여 문제를 해결 할 수 있다. (투 포인터에 대해서 궁금하다면 밑의 링크를 클릭해서 바킹독님의 강의를 보면 된다. 이 문제에 대한 풀이도 해주신다!) https://www.youtube.com/watch?v=I_0aAKzu0m8&list=PLtqbFd2VIQv4O6D6l9HcD732hdrnYb6CY&index=21 포인터 두 개 st, en을 둔다. 1...
