[백준 - 1699번] 제곱수의 합 - Java //Wello Horld//

이번에는 백준 알고리즘의 1699번 문제 "제곱수의 합을" 풀어보도록 하자

이번문제에서 사용할 알고리즘은 다이나믹 프로그래밍이다. 또한, 어느정도의 수학적으로 접근법만 알고 있으면 쉬운 문제이다.

일단, 이 문제를 처음보고 아래 첨부한 것과 같이 반복문 안에다가 입력값 N을 루트를 때려버리고 그 값을 빼가면서 반복문을 돌린 횟수로 답을 구하는 알고리즘을 작성한 후 제출한 결과 틀렸다는 걸 알았는데,

import java.io.*;
import java.util.*;

public class sample {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());
        int cnt = 0;
        while(N != 0){
            int temp = (int) Math.sqrt(N);
            N -= Math.pow(temp, 2);
            System.out.println(temp);
            cnt++;
        }
        bw.write(cnt + "\n");


        bw.flush();
        br.close();
        bw.close();
    }
}

위 코드가 틀린 이유는 위의 코드로 N = 18일 때, 18 = 4^4 + 1^1 + 1^1 로 답이 3이 나온다. 하지만,  답은 18 = 3^2 + 3^2 이므로, 위의 코드는 이번 문제를 푸는데 적절하지 않다는 것을 알 수 있었다.

그래서, 이번 문제를 푸는데, 다이나믹 프로그래밍을 이용해서 문제를 풀었다. 일단, 입력값 N 은 (1 <= N <= 100,000) 이므로, 317의 제곱값(100,489)보다 작으므로, 아래와 같이 세팅했다. 

int[] dp = new int[317 * 317 + 1];

또한, 입력값이 48일 때, 다이나믹 프로그래밍을 이용해서 문제를 풀려면, dp[32] + 1, dp[39] + 1, dp[44] + 1, dp[47] + 1 중에서 값이 가장 작은 것을 고르면 된다. 해서, helper라고하는 정수 배열을 [317 + 1] 만큼의 크기로 만들어서, 문제를 푸는데 도움을 줄 수 있도록 했다.

성공한 코드 전문은 아래와 같다.

import java.io.*;
import java.util.*;

public class sample {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());
        int[] dp = new int[317 * 317 + 1];
        int[] helper = new int[317 + 1];
        for(int i = 1; i <= 317; i++){
            helper[i] = i * i;
            dp[i * i] = 1;
        }
        for(int i = 2; i <= N + 1; i++){
            if(dp[i] != 0) continue;
            dp[i] = 317;
            for(int j = 1; 0 < i - helper[j]; j++){
                dp[i] = Math.min(dp[i], dp[i - helper[j]] + 1);
            }
        }
        bw.write(dp[N] + "\n");

        bw.flush();
        br.close();
        bw.close();
    }
}

 

1699번: 제곱수의 합

출처 : https://www.acmicpc.net/problem/1699