[프로그래머스 Summer/Winter Coding] 소수 만들기 -Java

https://programmers.co.kr/learn/courses/30/lessons/12977

코딩테스트 연습 - 소수 만들기

class Solution {
		int answer;
		int arr[];
	    public int solution(int[] nums) {
	        answer = 0;
	        arr=new int[3];
	        dfs(nums,nums.length,0,0,0);
	        return answer;
	    }

		private void dfs(int[] nums, int len, int cnt, int sum,int start) {
			if(cnt==3) {
				if(sum%2==0) return;
				
				for(int i=2; i*i<=sum; i++) {
					if(sum%i==0) return;
				}
				answer++;
				return ;
			}
			
			for(int i=start; i<len; i++) {
				arr[cnt]=nums[i];
				dfs(nums,len,cnt+1,sum+nums[i],i+1);
			}
		}
	}

소요시간 : 15분

 

dfs를 통해서 숫자 3개를 선택했습니다.

 

그리고 만약 3개의 숫자의 합이 짝수라면 return을 통해 다음 조합으로 넘어가줍니다.

 

짝수가 아니라면 소수를 판별합니다.

 

소수를 판별할 때 i*i<sum 이라는 조건을 사용하였습니다.

 

만약 소수를 판별할 수가 12이라면 12의 약수로는

 

1, 2, 3, 4, 6, 12 가 나옵니다.

 

1은 12와 

2는 6과

3은 4와 짝을 이루고 있습니다.

 

이 때 12의 제곱근인 3.xxxx가 넘어갈 때까지 12가 나누어지지 않는다면 이는 소수로 판별할 수 있습니다!