[BOJ] 백준 1644 소수의 연속합 (Swift)

문제

https://www.acmicpc.net/problem/1644

1644번: 소수의 연속합

풀이

투 포인터 알고리즘으로 풀 수 있는 문제입니다.

1806 부분합 문제와 거의 동일하고, 소수만 구해주면 되는 문제입니다.

먼저 n보다 작거나 같은 소수들을 모두 구해주어야 합니다.
저는 에라토스테네스의 체 알고리즘을 사용하여 구했습니다.

그 이후 이 소수들에 대해서 투 포인터를 사용하여 부분합을 구해줍시다.

왼쪽에 포인터를 2개 두고,
소수들에 대해서 n보다 크거나 같아질 때 까지, 왼쪽의 포인터를 왼쪽으로 하나씩 옮기면서 더해줍시다.

n이랑 같아졌다면, count를 1 증가시켜줍시다.

n보다 커졌다면, 나머지 하나의 포인터가 가르키는 요소를 빼주고,
포인터를 왼쪽으로 옮겨줍시다.

모든 포인터가 오른쪽으로 옮겨질 때 까지 반복해주면
연속된 소수의 합으로 나타낼 수 있는 경우의 수를 구할 수 있습니다.

소스코드

후기

1806 부분합 문제를 이미 풀어봤기 때문에 쉽게 풀 수 있었던 문제였습니다.