블루 브리지 컵 - 알고리즘 향상: 사탕 가져오기(동적 기획)

문제 설명
엄마가 B 군에게 N 사탕을 사주셨다!하지만 그녀는 B 군이 직접 먹는 것을 허락하지 않았다.
만약에 현재 M 덩어리 설탕이 있다고 가정하면 작은 B는 매번 P 덩어리 설탕을 들 수 있는데 그 중에서 P는 M의 뿌리 아래 M보다 크지 않은 질인수이다.이때 엄마는 B군이 P사탕을 가져간 뒤 다시 사탕 더미에서 P사탕을 가져간다.그리고 작은 B는 이어서 사탕을 꺼낼 수 있다.
지금 B군은 설탕을 얼마나 많이 받을 수 있는지 알고 싶어 한다.
입력 형식
하나의 정수 N
출력 형식
설탕 최대 얼마까지 들 수 있어요?
샘플 입력
15
샘플 출력
6
데이터 크기 및 규약
　　N <= 100000
나의 사고방식: dp로 이 문제를 푸는 것은 매우 간단하다. 4부터 각 개수에서 얻을 수 있는 최대 수를 계산한다. 1은 질수가 아니라 2.3의 근호 뒤에 1이 있기 때문에 4부터 계산한다.
핵심 알고리즘
max[i-2*j]+j>max[i]i는 현재 총수입니다.

import java.util.Scanner;

public class     {
	static int max[];
	public static void main(String[]args){
		Scanner s=new Scanner(System.in);
		int n=s.nextInt();
		max=new int[n+1];
		rest(n);
		System.out.println(max[n]);
	}
	public static void rest(int n){
		for(int i=4;i<=n;i++){
			int x=(int)Math.sqrt(i);
			for(int j=2;j<=x;j++){
				if(x%j==0&&judge(j)&&max[i-2*j]+j>max[i])
					max[i]=max[i-2*j]+j;
			}
		}
	}
	public static boolean judge(int n){
		for(int i=2;i<=n/2;i++){
			if(n%i==0)
				return false;
		}
		return true;
	}
}