BOJ-17626 ) Four Squares

---

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

17626번: Four Squares

---

현재의 값이 어떤 제곱수보다 커서 빼질 수 있다면, 그 제곱수의 값에 +1을 해주어

 

항상 최소를 만족한다

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class BOJ_17626 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int dp[] = new int[n+1];
		for(int i=1;i<=n;i++) {
			dp[i] = 987654321;
		}
		
		for(int i=0;i<=n;i++) {
			for(int j=1;j*j<=i;j++) {
				dp[i] = min(dp[i-j*j]+1,dp[i]);
			}
		}
		System.out.println(dp[n]);
	}

	private static int min(int i, int j) {
		return i>j?j:i;
	}
}

---