[BaekJoon] 1699번 제곱수의 합 (Java) 문제 풀이 [Sliver 2]

문제

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

1699번: 제곱수의 합

 

어떻게 풀 것인가?

수학적인 요건이 필요한가? 싶어서 처음에는 당황스러웠다. 

 

하지만 전형적인 DP스러운 문제였다.

 

자 우리가 원하는건 제곱수 항의 최소 개수이다. 그렇다면 주어진 N의 제곱수 최대 크기의 제곱근까지 번복해서 비교하여 작은 값을 넣는 것을 반복하면 되지 않을까?

 

말로는 어렵지만, 코드로 보면 단박에 이해가 될 것이다.

 

풀면서 놓쳤던점

DP는 어렵다... 매우 어렵다.. 

 

이 문제를 통해 얻어갈 것

DP

 

내 코드 

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

public class Main {
    static int[] dp;
    static int n;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        dp = new int[n + 1];
        calculate();

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

    private static void calculate() {
        // dp[i]를 i를 제곱수의 합으로 표현할 때 필요한 최소 항의 개수라고 정의
        // 초기값은 모두 무한대(INF)로 설정
        for (int i = 1; i <= n; i++) {
            dp[i] = Integer.MAX_VALUE;
        }

        // 1부터 n까지의 모든 수에 대해 최소 항의 개수 계산
        for (int i = 1; i <= n; i++) {
            // 제곱수의 최대 크기는 i의 제곱근까지이므로 j*j가 i보다 작은 범위까지 반복
            for (int j = 1; j * j <= i; j++) {
                dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
            }
        }
    }
}

 

참고

X