백준 : 제곱수들의 합(1699) with 자바

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

1699번: 제곱수의 합

 

제목그데로 숫자 N이 주어졌을 때 N의 제곱수들의 합인 최솟값을 구하는 문제이다.

위에 적은 제곱수들이 주어진 N에 대한 최솟값의 제곱수들로 이루어진 수이다.

 

예제를 분석해보았다.

public static void main(String[] args) {

       Scanner sc = new Scanner(System.in);

       int N = sc.nextInt();

       int[] dp = new int[N + 1]; // dp 배열 크기를 N + 1로 설정

       dp[0] = 0;

       for (int i = 1; i <= N; i++) {

              dp[i] = 100001;

              for (int j = 1; j * j <= i; j++) { // j*j가 i 이하인 범위까지만 고려

                    dp[i] = Math.min(dp[i], dp[i - j * j] + 1);

              }

      }

      System.out.println(dp[N]); // dp[N] 출력

}

코드가 간단하니 나눠서 설명하지 않고 한번에 설명하겠다.

먼저 스캐너 객체를 생성한뒤, N에 입력값을 입력받는다.

그리고 빈배열 dp를 생성하고 크기를 N + 1로 지정한다.

dp[0] = 0 이라고 고정을 한뒤, dp[i]의 값을 반복문을 통해서 구하려 한다.

임시배열 i를 생성하고 반복문을 한번 돌린 뒤 dp[i] = 100001의 범위를 지정한다. 문제 조건에서 자연수의 범위가  (1 ≤ N ≤ 100,000)라고 되어있으므로 이렇게 지정하였다.

임시배열 j를생성하고 반복문을 한번 더돌려서  dp[i], dp[i - j^2 + 1] 의 최솟값을 구해서 dp[i]dㅔ 저장할 것이다. 그러면 제곱수의 최솟값이 dp[]에 저장 될 것이다.

저장된 dp[N]의 최솟값을 을 출력한다.