Cos Pro 1급 - 샘플 문제 풀이 3차 6번 (n이하의 소수를 찾아 더하기)

문제 지문 #6

어떤 수를 서로 다른 소수 3개의 합으로 표현하는 방법의 수를 구하려 합니다.

예를 들어 33은 총 4가지 방법으로 표현할 수 있습니다.

1. 3+7+23
2. 3+11+19
3. 3+13+17
4. 5+11+17

자연수 n이 매개변수로 주어질 때, n을 서로 다른 소수 3개의 합으로 표현하는 방법의 수를 return 하도록 solution 메서드를 작성하려 합니다. 빈칸을 채워 전체 코드를 완성해주세요.

※ 1,000 이하인 소수는 168개 있습니다.

---

매개변수 설명

n이 solution 메서드의 매개변수로 주어집니다.

• n은 1,000 이하인 자연수입니다.

---

return 값 설명

n을 서로 다른 소수 3개의 합으로 표현하는 방법의 수를 return 해주세요.

• 만약, n을 서로 다른 소수 3개의 합으로 표현할 수 없다면 0을 return 해주세요.

---

예시

n	return
33	4
9	0

 

예시 설명

예시 #1
문제에 나온 예와 같습니다.

예시 #2
9는 서로 다른 세 소수의 합으로 나타낼 수 없습니다.

728x90

 

혼자 풀이

빈칸 채우기 문제입니다. n이하의 소수를 찾아 primes에 저장하는 부분과, primes의 값을 순차적으로 더해서 n과 일치하는지 확인하는 부분으로 나뉘어있습니다.
소수는 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수입니다. 이 특성을 잘 이해하면 코드를 이해할 수 있습니다.

import java.util.ArrayList;

class MySolution {
    public int solution(int n) {
        int answer = 0;
        ArrayList<Integer> primes = new ArrayList<Integer>();
        primes.add(2); //첫번째 소수인 2를 primes에 저장
        for (int i = 3; i <= n; i += 2) { //소수는 3이상의 홀수 중에 있음
            boolean isPrime = true;
            for (int j = 2; j < i; j++)  //i를 i보다 작은 j로 나누었을때 나머지가 0이면 소수가 아니므로 break;
                if (i % j == 0){
                    isPrime = false;
                    break;
                }
//            if (@@@)
            if (isPrime)  // for문이 break로 종료되지 않았으면 i는 소수
                primes.add(i);
        }
        //primes의 모든 원소에 대해 순차적으로 합계를 구해 n과 일치하면 answer를 1증가
        int primeLen = primes.size();
        for (int i = 0; i < primeLen - 2; i++)
            for (int j = i + 1; j < primeLen - 1; j++)
                for (int k = j + 1; k < primeLen; k++)
//                    if (@@@)
                    if ( primes.get(i)+primes.get(j)+primes.get(k)==n)
                        answer++;
        return answer;
    }
    
    // 아래는 테스트케이스 출력을 해보기 위한 main 메소드입니다.    
    public static void main(String[] args) {
    	MySolution sol = new MySolution();
        int n1 = 33;
        int ret1 = sol.solution(n1);

        // [실행] 버튼을 누르면 출력 값을 볼 수 있습니다.
        System.out.println("solution 메소드의 반환 값은 " + ret1 + " 입니다.");
        
        int n2 = 9;
        int ret2 = sol.solution(n2);

        // [실행] 버튼을 누르면 출력 값을 볼 수 있습니다.
        System.out.println("solution 메소드의 반환 값은 " + ret2 + " 입니다.");
    }    
}

 

정답

정답이 문제와 좀 다릅니다. 공식 홈에서 받았는데, 이렇게 다른 것이 있다니.. ;;
코드만 보자면, for문이 모두 수행되면 i는 i보다 작은 어떤 j로도 나눠지지 않았고, i==j가 되므로 이 조건으로 소수를 찾았습니다.

import java.util.ArrayList;

class CorrectSolution {
    public int solution(int n) {
        int answer = 0;
        int i, j, k;
        ArrayList<Integer> prime = new ArrayList<Integer>();
        prime.add(2);
        for (i = 3; i <= n; i += 2) {
            for (j = 2; j < i; j++) {
                if (i % j == 0) {
                    break;
                }
            }
            if (j == i) {
                prime.add(i);
            }
        }
        int prime_n = prime.size();
        for (i = 0; i < prime_n - 2; i++) {
            for (j = i + 1; j < prime_n - 1; j++) {
                for (k = j + 1; k < prime_n; k++) {
                    if (prime.get(i) + prime.get(j) + prime.get(k) == n) {
                        answer += 1;
                    }
                }
            }
        }
        return answer;
    }    
}

 

첨부 파일

프로젝트 파일 전체를 첨부합니다.
Solution 이 문제, CorrectSolution 이 정답, MySolution이 제가 푼 것입니다.
"Project from existing sources..." 메뉴에서 불러다 쓰시면 됩니다.

ThirdQuestion6.zip

0.01MB

출처: https://www.ybmit.com/cos_pro/cos_pro_r_test.jsp