[백준/1699] 제곱수의 합 (Java/코드)

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

---

제곱수의 합 성공

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128 MB	13176	5386	3988	40.810%

문제

어떤 자연수 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)

출력

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

예제 입력 1 

7

예제 출력 1 

4

---

런타임 오류는 역시나 배열 설정할때 나는 오류다.

int[] d= new int[n+1]; 로 했더니, 런타임 오류가 발생했다.

백준저지 틀렸습니다. 라고 나온 원인은

분기 설정이라던가, 사소한 범위 차이에서 발생한다.

나같은 경우는 아래 코드의 표시된 부분에 발생했는데, 현재 저장한 d[i]보다 새로히 저장할 d[i - j*j] +1이 더 작을경우에만

저장하도록 분기를 세우는 부분이다.

import java.util.*;
public class Main{
 
    public static void main(String[] args){
        
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] d = new int[100001];
    
        d[0]=0;
        d[1]=1;
        d[2]=2;
 
        for(int i=3 ;i<=n ; i++)
            d[i]=99;
       
        for(int i=3; i<=n ; i++){
           for(int j=1; j*j<=i ; j++){
               
                    if(d[i]>d[i-j*j]+1){
                        d[i]=d[i-j*j]+1;
                    }
                
           }
        }
 
       System.out.println(d[n]);
       }
    
}