[백준 JAVA] 17626 Four Squares

17626 Four Squares

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

문제설명

주어진 정수를 제곱수의 합으로 표현할 때, 필요한 제곱수의 최소 개수를 찾는다.

(제곱수: 1의 배수, 2의 배수, 3의 배수... 배수들을 의미)

접근방식

O(n * sqrt(n)) 시간복잡도

 

• • 두 개의 루프가 중첩되기 때문에 외부 루프는 n회, 내부 루프는 sqrt(n)회 반복된다.

문제 조건 분석 과정

• • 동적 계획법 (DP) 사용:
    • dp[i]는 정수 i를 제곱수의 합으로 표현할 때 필요한 최소 제곱수의 개수를 나타낸다.
  • 제곱수 배열 생성:
    • squares[i] 배열은 1부터 sqrt(n)까지의 모든 제곱수를 저장한다.
  • DP 배열 초기화:
    • dp[0]을 0으로 초기화한다. (0은 제곱수의 합으로 표현할 필요가 없다.)
    • 나머지 dp[i]를 매우 큰 값(최댓값)으로 초기화한다.
    • 이는 최소 제곱수를 찾기 위해 비교할 때 기본값으로 사용된다.
  • DP 배열 업데이트:
    • 각 정수 i에 대해, 가능한 모든 제곱수를 사용하여 dp[i] 값을 업데이트한다.
    • 제곱수 j를 사용하여 dp[i]는 dp[i - squares[j]] + 1로 갱신된다.
    • 이는 i를 만들기 위해 squares[j]를 사용하고, 나머지 i - squares[j]를 만들기 위해
    • 필요한 최소 제곱수 개수를 더하는 방식이다.

전체코드

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

public class Main_17626Four {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine().trim());

        //dp[i] = i를 제곱수의 합일때 필요한 최소 제곱수
        int[] dp = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            dp[i] = Integer.MAX_VALUE; //기본값 = 최댓값
        }
        dp[0] = 0;

        // squares[i] = i의 제곱수
        int[] squares = new int[(int) Math.sqrt(n) + 1];
        for (int i = 1; i <= Math.sqrt(n); i++) {
            squares[i] = i * i;
        }

        //dp 배열 반복문
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j < squares.length; j++) {
                //제곱수가 현재 인덱스보다 클 경우
                if (squares[j] > i) break;
                //현재 dp[i] 업데이트
                //dp[i - squares[j]] + 1 = 현재 제곱수
                dp[i] = Math.min(dp[i], dp[i - squares[j]] + 1);
            }
        }

        System.out.println(dp[n]);
        br.readLine();
    }
}