백준 1699 제곱수의 합 Java

정답률 41퍼센트의 dp 문제이다.

왜 41퍼센트인지 모를 정도로 점화식 세우기가 어려웠다..

 

마지막 자리에 올 수 있는 수는 1^2, 2^2, 3^2 등등 어떤수의 제곱인 i^2이다.

그리고 i^2 앞에는 n-i^2이다.

뒤에 i^2이 왔으니 n에 i^2을 빼야 하는 것이다.

그리고 dp배열에는 최종적으로 항의 개수가 들어가야 한다. 

최종적으로 식은 n-i^2+i^2이므로 항 n-i^2에 +1을 해줘야 한다.

 

무슨소리인지 이해하기 힘들지만 이해하려고 하면 이해가 된다.

그렇게 점화식을 세우면 dp[n] = Math.min(dp[n-i^2]+1) //가능한 i범위 중에서 최소값

저렇게 세워진다. 

 

public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int [] dp = new int[n+1];
        
        for(int i=1; i<=n; i++) {
            dp[i] = i;
            for(int j=1; j*j <= i; j++) 
                if(dp[i] > dp[i-j*j]+1)
                    dp[i] = dp[i-j*j]+1;
        }
        System.out.println(dp[n]);
    }