백준 1699번 제곱수의 합 [JAVA]

문제

어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다. 이 경우, 수학자 숌크라테스는 “11은 3개 항의 제곱수 합으로 표현할 수 있다.”라고 말한다. 또한 11은 그보다 적은 항의 제곱수 합으로 표현할 수 없으므로, 11을 그 합으로써 표현할 수 있는 제곱수 항의 최소 개수는 3이다.

주어진 자연수 N을 이렇게 제곱수들의 합으로 표현할 때에 그 항의 최소개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 100,000)

출력

주어진 자연수를 제곱수의 합으로 나타낼 때에 그 제곱수 항의 최소 개수를 출력한다.

 

 

 

이 문제는 비교적 점화식을 도출하기 쉬운 문제였다 하지만 내가 잘했다기 보단 그냥 문제가 좀 무난했던거같다

 

 

알고리즘 설계 

 

일단 어떤 수 N을 최소 개수의 제곱수의 합으로 나타내라고 했을때 가장 먼저 떠오른 아이디어는

N=1^2+()

N=2^2+()

N=3^2+() 이다 

-----(생략)

 

즉. N이 되기 직전에 어떤 제곱수의 합으로 N이 된건지 case를 따려주고 

그 모든 case에서 최솟값이 바로 N을 제곱수로 나타낼수 있는데 최소 항의 개수이다 

 

dp[i]=i를 제곱수의 합으로 나타낼때 최소 항의 개수 

-> 정의를 잘 파악해야한다 최소 항의 개수인지 아니면 예를 들어 제곱수의 종류인지 등등 머리에 박아놓고 문제를 계속 풀어나가야 한다

 

일단 dp[0]=0, dp[1]=1이다 이제 2부터 우리가 구할려고하는 N까지 for문을 이용해서 bottom up방식으로 dp[N]을 구해주면 된다 

 

dp[10]=1^2+dp[9] OR 2^2+dp[6] OR 3^2+dp[1]이고

1^2이든 2^2이든 3^2이든 항의 개수는 1개이므로   

결론적으로 1+dp[9] OR 1+dp[6] OR 1+dp[1]중에 최솟값이 dp[10]이다 

 

모든 문제가 다 그런건 아니지만 이 문제같은경우엔 1부터 어느정도의 수까지 식을 나열하면 규칙을 찾는 방식으로 점화식을 도축할수 있는 문제였다. 이런경우엔 난이도가 쉬운경우에 속한다

 

 

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

        dp[0]=0;
        dp[1]=1;

        for(int i=2;i<=n;i++){
            int min=i; 
            for(int j=1;j*j<=i;j++){
                if(min>dp[i-(j*j)]+1)
                    min=dp[i-(j*j)]+1;
            }
            dp[i]=min;
        }

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

 

 

처음에 min값을 무턱대고  10000으로 초기화 했다고 틀렸다. 물론 틀릴줄 알았다  

여러 수중에서 최솟값을 구하기 위해 처음에 min값을 초기화 해줄때 고민이 많이 되는데

최대한 논리적으로 접근하면 금방 알 수 있다

min의 최댓값은 i이다 예를 들어 dp[10] 의 최댓값(최악의 경우)은

i^2+ i^2+ i^2+ i^2+ i^2+ i^2+ i^2+ i^2+ i^2+ i^2 (총 i개 이기 때문이다)