[백준] no17626: Four Squares

문제

모든 자연수 N은 최대 4개의 제곱수의 합과 같다는 것을 증명하는 문제.

따라서, 임의의 자연수 N이 주어질 때, 1개부터 4개까지의 숫자를 각각 제곱하여 더해줬을 때,

합이 N이 되는 경우 사용된 제곱근의 개수를 구하는 문제

---

원리

방법1. 브루트 포스 (경우의 수를 순차적으로 다 때려 박는 방법 = 하드웨어 성능에 의존하는 방식)

    /**
     * 브루트 포스
     * 1. 1부터 제곱
     * 2. 제곱이 N보다 크면, 다음 차례로 넘어감
     * 3. 1부터 제곱 + 1부터 제곱 의 반복
     * 4. 합이 N보다 크면, 다음 차례로 넘어감
     * 5. 이런식으로 총 4개까지 진행
     * 6. 중간에 같은 수가 나오면, 제곱을 위해 더한 개수를 출력
     */

방법2. DP (성능 최적화)

    /**
     * DP
     * 1. 합산한 숫자를 넣어둘 배열을 만듦. 이때, 참조변수타입으로 만들면 전부 null로 초기화됨
     * 2. 반복을 하면서 해당 자리가 null이 아닌 경우엔 이미 알아봤던 합산이므로 계산하지 않고 넘김
     */

 

---

풀이방법

방법1. 브루트 포스

    /**
     * 최대 4개까지의 수를 제곱해서 합해줄 것이므로, 3개의 반복문을 사용
     * 만약 3개의 반복문 안에 해결이 안되면 4개를 사용해야하므로, 따로 계산 하지 않고 바로 4를 반환
     * 각 반복문에서 사용하는 변수 i,j,k를 이용해 각 변수에 1씩 더해서 제곱해주는 방식으로 합을 확인
     * i,j,k 각각의 제곱의 합(sum)이 목표 자연수(N)에 도달했을때, 각 자리수가 몇개 사용했는지 확인해서 결과를 반환
     * @return 사용한 숫자의 개수
     */

방법2. DP

/**
 * 합산 후, 만약 방문한 적이 없는 경우에만 DP 배열에 값을 입력 후(이제 null이 아니게 됨)
 * 목표값(N)과 비교하는 if문을 적용
 */

 

 

---

나의 코드

1. 브루트 포스 [14228kb / 176ms -> 생각보다 빠름]

    private static double N; // 최종 목표가 될 임의로 들어오는 자연수. static 메소드에서 사용하기 위해 static 변수로 받음

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine()); // 입력받은 자연수를 static 변수에 할당해주는 구간
        System.out.println(brute()); // static 메소드를 호출해서 결과 출력
    }

    /**
     * @return 사용한 숫자의 개수
     */
    private static int brute () {
        int result = 4; // 3번의 반복을 수행하고도 안되면 나머진 전부 4개 쓴거임
        int sqrtN = (int) Math.sqrt(N); // 반복은 최대 N의 제곱근까지임. 그 이상은 N을 넘어가므로

        // * 주의할 점 : 0부터 N제곱근과 같은 숫자까지 반복해야함. (0은 안쓴경우, first < sqrtN은 sqrtN이 포함 안되므로 주의)
        for(int third = 0; third <= sqrtN; third++) {
            for(int second = 0; second <= sqrtN; second++) {
                for(int first = 0; first <= sqrtN; first++) {
                    double sum = Math.pow(first, 2) + Math.pow(second, 2) + Math.pow(third, 2);
                    if(sum==N) {  // 각 제곱의 합이 N에 도달했을 때,
                        if(third!=0) return 3; // 3개까지 썼을 경우
                        else if (second!=0) return 2; // 2개까지 썼을 경우
                        else return 1; // 1개만 썼을 경우
                    }
                }
            }
        }

        return result;
    }

 

2. DP [15456kb / 192ms -> 의외로 더 느림]

: 로직의 불필요한 반복을 스킵했으나, 스킵을 위한 판정과 변수선언이 들어감으로써 오히려 부하가 더 늘어남

private static double N; // 최종 목표가 될 임의로 들어오는 자연수. static 메소드에서 사용하기 위해 static 변수로 받음
private static Double[] DP; // DP용 배열

public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    N = Integer.parseInt(br.readLine()); // 입력받은 자연수를 static 변수에 할당해주는 구간
    DP = new Double [50001]; // 문제에서 제한이 N <= 50000
    
    System.out.println(DP());
}

/**
 * @return 사용한 숫자의 개수
 */
private static int DP () {
    int result = 4; // 3번의 반복을 수행하고도 안되면 나머진 전부 4개 쓴거임
    int sqrtN = (int) Math.sqrt(N); // 반복은 최대 N의 제곱근까지임. 그 이상은 N을 넘어가므로

    // * 주의할 점 : 0부터 N제곱근과 같은 숫자까지 반복해야함. (0은 안쓴경우, first < sqrtN은 sqrtN이 포함 안되므로 주의)
    for(int third = 0; third <= sqrtN; third++) {
        for(int second = 0; second <= sqrtN; second++) {
            for(int first = 0; first <= sqrtN; first++) {
                double sum = Math.pow(first, 2) + Math.pow(second, 2) + Math.pow(third, 2);
                if(sum<=50000 && DP[(int) sum]==null) {
                    DP[(int) sum] = sum;
                    if (sum == N) {  // 각 제곱의 합이 N에 도달했을 때,
                        if (third != 0) return 3; // 3개까지 썼을 경우
                        else if (second != 0) return 2; // 2개까지 썼을 경우
                        else return 1; // 1개만 썼을 경우
                    }
                }
            }
        }
    }
    return result;
}