[Baekjoon] 17626: Four Squares

문제

특정 숫자의 제곱수 합을 구할 때 그 수들의 최소 개수를 구하는 문제이다.

 

풀이

내 풀이

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

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

        int n = Integer.parseInt(br.readLine());
        int[] dp = new int[n + 1];
        dp[1] = 1;

        int sqrt = 2;
        for (int i = 2; i <= n; i++) {
            if (i == Math.pow(sqrt, 2)) {
                dp[i] = 1;
                sqrt++;
                continue;
            }

            int minCount = 5;
            for (int j = 1; j*j < i; j++) {
                int count = dp[i - j*j] + 1;
                minCount = Math.min(minCount, count);
            }

            dp[i] = minCount;
        }

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

결국 풀이하지 못해 검색을 통해 힌트를 얻었다.

 

아이디어는 다음과 같다.

 

해당 숫자보다 작은 제곱수들을 돌면서 해당 숫자에서 제곱수를 뺀 값의 합 개수를 확인한다.

 

예를 들어, 현재 숫자가 27이라고 하면

1, 4, 9, 16, 25의 제곱수까지 돌면서 27에서 이 제곱수들을 뺀 값의 합 개수를 본다.

즉, 26(27-1), 23(27-4), 18(27-9), 11(27-16), 2(27-25)의 값을 확인한다.

여기서 최소 개수를 구한 다음 1을 더해준다. (제곱수에서 뺏기 때문에 제곱수 개수를 포함한 값인 1을 더한다)

 

그러면 최소 개수는 2이기 때문에 최종적으로 답은 3이 나올 것이다.

 

회고

실버3 문제였지만, 결국 못풀고 확인했다. dp문제는 역시 아직 좀 어려운 것 같다.

더 많은 문제를 풀면서 기초를 다져야겠다.