백준 1699번

1699번: 제곱수의 합

 

가장 적은 제곱수 개수를 이용해서 주어진 n을 표현하는 방법의 알고리즘이다.

 

풀이

LIS 알고리즘과 비슷하게 접근을 하면 될 것 같다고 생각하였고
느낌적인 느낌상 n보다 작은 제곱수중에 가장 큰 수로 무조건 하게 되면 반례가 있을  것 같다고 생각하였다.

 

arr	1	2
dp	1	2

 우선 가장먼저 해야 할 것은 n보다 작은 제곱수들을 찾는 것이라고 생각하였다.

 2를 예로 들면 2는 1의 제곱수만 가능하기 때문에 2 - (1*1)을 하면 1이 나오게 된다.

1에는 제곱수로 나타낼 수 있는 최소 개수인 1이 있는 상태이다. 그러므로 1+1을 해주면 2에는 2가 들어가게 된다.

 

3도 마찬가지로 2의 2승보다 작기 때문에 1 제곱수만 가능하다

dp [3] = dp[3 - (1*1)] + 1을 하면 3의 최소개수의 제곱수의 개수인 3이 나온다. 

3 = {1*1 + 1*1 + 1*1}

 

여기까지만 생각하면 점화식이

int x = n과 가장 가까운 제곱수 - n

dp [n] = dp [x] + 1이라고 생각할 수 있다 

 

반례로 여러 가지 경우가 있지만 32의 숫자를 할 경우 이와 같은 식은 오류가 생긴다. 위와 같은 점화식으로 32의 제곱수를 구해보면

32 = {5*5 + 2*2 + 1*1 + 1*1 + 1*1}가 나온다. 하지만 정답은 {4*4, 4*4}인 2개의 항으로만 32의 숫자를 만들 수 있다.

 

 

그래서 반례를 처리하기 위해 

dp [ n - n보다 작은 제곱수들 ]들 중 가장 작은 값을 찾아낸다. 그렇게 찾아낸 가장 작은 값을 가진 제곱수의 dp + 1을 해주면 된다.

n이 32일 때를 예로 들면

dp [ (n - 1*1 )] = dp [31]

dp [ (n - 2*2 )] = dp [28]

dp [ (n - 3*3 )] = dp [23]

dp [ (n - 4*4 )] = dp [16]

dp [ (n - 5*5 )] = dp [7]

의 식들 중 가장 작은 값을 골라 +1을 해주면 반례가 처리된다.

 

 

 

코드

import java.util.*;
public class Main
{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n + 1];
        int[] dp = new int[n+1];

        for (int i = 1; i <= n; ++i)
        {
            arr[i] = i;
        }
        dp[1] = 1;

        for(int i = 2;i<=n;++i)
        {
            //arr[n]과 가장 근사치인 제곱근 구함.
            int x = 1;
            int minValue = arr[i];
            while (true)
            {
                if((x*x)>arr[i])
                {
                    break;
                }else {
                    int r = x*x;
                    int t = arr[i] - r;
                    minValue = Math.min(minValue,dp[t]);
                    ++x;
                }
            }
            dp[i] = minValue+1;
        }
        System.out.println(dp[n]);
    }

}