-
[백준] 1644 소수의 연속합 - Java알고리즘 문제 풀이 2024. 6. 16. 16:44
문제 - 소수의 연속합
https://www.acmicpc.net/problem/1644
접근 방법
이 문제는 투 포인터로 부분합을 구해서 만족하는 조건의 개수를 구하는 문제이다
{1,2,3,4,5} 이런 배열이 소수 배열 ex) {2,3,5,7,....}이런 걸로 바뀌었다
그래서 우선 target 이하의 소수들을 배열에 넣어서 구해야하고
그 소수 배열의 부분합을 구하면 될 것 같다
소수를 구할때 Math.sqrt()를 이용해서 2부터 제곱근 까지 나뉘어 지는지 판단하는 식으로 하면 될 것같다
제곱근까지 하는 이유가 만약 64까지 구한다고 하면 64의 제곱근인 8 이상으로 나눠 봤자 의미가 없기 때문이다
코드 작성
import java.util.ArrayList; import java.util.List; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int target = scanner.nextInt(); List<Integer> list = new ArrayList<>(); list.add(2); for (int i = 3; i <= target; i++) { if (isPrime(i)) { list.add(i); } } int start = 0; int end = 0; int sum = 0; int cnt = 0; while (true) { if (sum >= target) { sum -= list.get(start); start++; } else if (end == list.size()) { break; } else { sum += list.get(end); end++; } if (sum == target) { cnt++; } } System.out.println(cnt); } public static boolean isPrime(int number) { for (int i = 2; i <= Math.sqrt(number); i++) { if (number % i == 0) { return false; } } return true; } }
'알고리즘 문제 풀이' 카테고리의 다른 글
[백준] 11728 배열 합치기 - Java (0) 2024.06.24 [백준] 2644 촌수계산 - Java (0) 2024.06.03 [백준] 4963 섬의 개수 - Java (1) 2024.06.02 [백준] 1012 유기농 배추 - Java (0) 2024.05.30 [프로그래머스] 네트워크 - Java (0) 2024.05.30