[Java] 백준 11502번 : 세 개의 소수 문제

 

2960번 에라토스테네스의 체를 푸는 김에,

소수를 활용하는 문제를 하나 더 풀어보았습니다!  ⌯'▾'⌯ 

 

백준 11502번

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

11502번: 세 개의 소수 문제

 

주어진 숫자를 세 개의 소수 합으로 나타내는 문제입니다!

저는 이전 글에서 에라토스테네스의 체를 구하는 함수를 따로 짜뒀기 때문에, 그 함수를 활용하였습니다.

 

↓ (이전 문제가 궁금하면 참고하세요! )

https://wisdom-990629.tistory.com/entry/C-%EB%B0%B1%EC%A4%80-2960%EB%B2%88-%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98-%EC%B2%B4

[C] 백준 2960번 : 에라토스테네스의 체

 

import java.util.Scanner;

class Main 
{
	static boolean[] isPrime=new boolean[1001]; // false이면 소수, true이면 합성수
	static int[] primeList=new int[1001]; // 찾은 소수 모두 저장
	static int primeCnt; // primeList의 index

	public static void primeSieve(int n) // 소수 구하기
	{
    	// isPrime 배열 구하기
		for (int i = 2; i*i <= n; i++) 
			for (int j = i * i; j <= n; j += i)
				if (!isPrime[j]) 
					isPrime[j] = true;

		// primeList 배열 구하기
		for (int i = 2; i <= n; i++)
			if (!isPrime[i])
				primeList[primeCnt++] = i;
	}
	
    public static void main(String[] args) {
    	
    	Scanner input=new Scanner(System.in);
    	int T=input.nextInt();
    	
    	int[] testCase=new int[T];
    	int max = 0;
    	for (int i = 0; i < T; i++)
    	{
    		testCase[i]=input.nextInt();
    		if (testCase[i] > max)
    			max = testCase[i];
    	}

    	input.close();
    	
        // primeList 배열은 가장 큰 수까지만 구하면 됨
    	primeSieve(max);
  
    	for (int i = 0; i < T; i++) {
    		int cnt=0;
            
            // 2 + 2 + 홀수인 소수
    		if (!isPrime[testCase[i] - 4])
    		{
    			cnt++;
    			System.out.println(2+" "+ 2+" "+ (testCase[i] - 4));
    			continue;
    		}
    		
            // 홀수인 소수 3개로 이루어진 경우
    		outerloop:
    		for (int j = 1; j < primeCnt; j++) {
    			for (int k = 1; k < primeCnt; k++) {
    				for (int u = 1; u < primeCnt; u++) {
    					if (primeList[j]+primeList[k]+primeList[u]==testCase[i])
    					{
    						cnt++;
    						System.out.println(primeList[j]+" "+ primeList[k]+" "+primeList[u]);
    						break outerloop;
    					}
    				}
    			}
    		}
            // 3개의 소수로 이루어지지 않은 경우
    		if (cnt==0)
    			System.out.println(0);
    	}
    }
}

 

 코드는 다음과 같습니다!

소수인지 합성 수인지 구분하는 isPrime 배열을 만들고,

소수를 primeList 배열에 따로 저장을 해줍니다.

그리고 for문을 돌려서.....^^ 적절한 답을 찾습니다 !

사실 for문을 많이 쓰는 것을 좋아하진 않는데,

트리나 다른 방식을 사용해서 풀자니 문제가 좀 어려워질 것 같아

무작정 for문을 돌려봤습니다...ㅎ

( 대신 for문의 탐색범위를 줄이기 위해 primeList 배열을 따로 사용하였습니다. )

그리고 홀수인 소수만 사용한다고 하여 경우를 2가지로 나누어보았습니다.

짝수 + 짝수 + 홀수 -> 짝수인 소수는 2밖에 없기 때문에 2 + 2 + 소수로 표현 가능합니다.

홀수 + 홀수 + 홀수 -> 3중 for문을 사용하여 3 이상의 소수를 찾아나갑니다.

.

오늘은 C가 아닌 Java를 사용하였는데,

그 이유는 중첩 for문을 사용했기 때문입니다.

Java를 사용하면 제일 안쪽에 있는 for문을 나가고 싶을 때 

break outerloop; -> 이런 식으로 간편히 나갈 수 있습니다.

또한 배열을 사용하는 게 Java가 조금 더 편해서 이번 문제는 Java를 사용하여 풀어보았습니다 :)

.

다만,, Java로 백준 문제를 푼 게 처음이었는데,

C언어에 비해 채점이 조금 까다로웠습니다.

우선 class 이름이 무조건 Main 이어야 하고, public으로 설정하면 안 되는 것 같았습니다.

처음에 모르고 막 제출했다가 컴파일 에러에 런타임 에러까지 나왔답니다...

모두들 Java는 조심해서 풀도록 합시다....