[BOJ] 백준 1153 네 개의 소수 (JAVA)

소수판별 + 백트레킹

📑 문제

백준 1153 네 개의 소수

---

🌱 아이디어

소수판별 알고리즘으로 구한 소수와 백트래킹으로 답을 구하자!

 

골드바흐 추측을 통해 푸는 것이 가장 주류 풀이법인 것 같은데 골드바흐 추측을 알지 못하기 때문에

에라토스테네스의 체 + 백트레킹으로 문제를 풀었다.

 

성능차이는 골드바흐 추측을 통해 푸는 방법이 더 좋다. 아마도 백트레킹 특성상 시간초과가 날 수 있기 때문에

골드바흐 추측으로 푸는 것 같은데 가지치기를 잘 설정하면 시간초과는 전혀 걱정 안 해도 된다!

 

위 문제는 스페셜 저지 문제이며 여러 가지의 답 중 단 하나만 출력해도 답으로 인정해 준다 즉

 

38 = 5 + 7 + 13 + 13, 38 = 2 + 2 + 3 + 31 등 여러 가지 답 중 하나만 출력해도 무방하다

 

가장 큰 소수 값부터 차례대로 입력해서  4개의 소수의 합이 N과 같을 때 출력하면 된다. 

 

---

 

🌱 코드 및 풀이

소수를 구하고 prime 배열에 담는다 그 이유는 1~1,000,000의 모든 숫자 중 하나씩 소수가 아닌지 맞는지 판별하는 것은

시간초과를 유발할 수 있다. 그렇기 때문에 필요한 수(소수)만 담아준다

 

가지치기(백트레킹 리턴)는 답이 되지 않는 확정 조건으로 한다

1. 4개의 소수를 담기 전에 합이 N을 초과할 때.

2. 4개의 소수를 담았으나 합이 N과 같지 않을 때.

 

위 조건을 만족하기 위해선

소수의 가장 큰 수부터 넣어야 효과적으로 시간복잡도를 줄일 수 있다

 

그 이유는 가지치기를 진행할 때 4개의 소수를 다 담고 판별하는 것보다

4개의 소수를 담기 전 답이 될 가능성이 보이지 않을 때 리턴하는 것이 시간을 절약할 수 있기 때문이다

 

그렇기에 소수의 합이 N의 초과를 유도할 수 있게 가장 큰 소수부터 담는 것이다.

---

🌱 느낀 점

 

골드 3 난이도에 비해 어려운 문제는 아니었다. 아마도 골드바흐 추측을 응용할 때 그 정도 난이도가 나오는 것 같다

 

만약 N 이 1,000,000보다 더 컸다면 나도 시간초과가 났을 것이라 생각한다.

생각해 보니 풀이법에 그리디 느낌도 나는 것 같다 ㅎㅎ

소수판별 방법을 여러 가지 익혀야겠다.