[BOJ] 백준 1153 네 개의 소수 (JAVA)
Algorithm/- Baekjoon2024. 3. 14. 17:18[BOJ] 백준 1153 네 개의 소수 (JAVA)

📑 문제🌱 아이디어소수판별 알고리즘으로 구한 소수와 백트래킹으로 답을 구하자! 골드바흐 추측을 통해 푸는 것이 가장 주류 풀이법인 것 같은데 골드바흐 추측을 알지 못하기 때문에에라토스테네스의 체 + 백트레킹으로 문제를 풀었다. 성능차이는 골드바흐 추측을 통해 푸는 방법이 더 좋다. 아마도 백트레킹 특성상 시간초과가 날 수 있기 때문에골드바흐 추측으로 푸는 것 같은데 가지치기를 잘 설정하면 시간초과는 전혀 걱정 안 해도 된다! 위 문제는 스페셜 저지 문제이며 여러 가지의 답 중 단 하나만 출력해도 답으로 인정해 준다 즉 38 = 5 + 7 + 13 + 13, 38 = 2 + 2 + 3 + 31 등 여러 가지 답 중 하나만 출력해도 무방하다 가장 큰 소수 값부터 차례대로 입력해서  4개의 소수의 합이 N..

image