[백준] 17626 Four Squares - Java

 

 

 

문제 출저

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

17626번: Four Squares

 

 

 

문제 풀이

자연수의 숫자 n이 주어진다.

이 n을 제곱수로 표현할 때, 제곱수의 최소 갯수를 구해야 한다.

제곱수란 1, 4, 9  ... 와 같은 자연수의 제곱으로 만드는 숫자이다. 

 

 

DP를 이용해서 풀었습니다. 

n의 범위는 1부터 50,000 입니다. int[] dp = new int[50001]을 선언했습니다.

dp 배열에 각 숫자의 제곱수의 최소값을 업데이트하여 최소값을 구했습니다. 

최소값은 이중 포문을 이용해서 구했습니다. 

50000의 이하의 최대 제곱수는 223의 제곱인 49729입니다.

1부터 223까지의 제곱수를 구해 int d에 저장했습니다.

그 다음 d부터 50000까지 인덱스를 탐색하여 dp[j] = Math.min(dp[j], dp[j-d] + 1) 연산을 통해 최소 제곱수 값을 업데이트 했습니다. 

이 과정을 거치면 dp[n]으로 정답을 구할 수 있습니다.

 

 

 

소스 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/*
Four Squares
https://www.acmicpc.net/problem/17626

재료는 제곱수

시간복잡도 : 50000 * 223 = 11,150,000 (대략 천만)
1초 = 1억번 연산 (10^8)
0.5초 = 5천만

시간 복잡도가 충분하다.


 */

public class Main {

    static int[] dp;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        dp = new int[50001];
        for(int i = 1; i < 50001; i++) {
            dp[i] = i;
        }


        int sqrt = (int) Math.sqrt(50000);
        System.out.println(sqrt);
        for(int i = 1; i <= sqrt; i++) {
            int d = i*i;
            dp[d] = 1;

            for(int j = d+1; j < 50001; j++) {
                dp[j] = Math.min(dp[j], dp[j-d] + 1);
            }

        }

        System.out.println(dp[n]);

    }
}