(백준, BOJ 17626) Four Squares(자바)

by

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

17626호: 포 스퀘어

라그랑주는 1770년에 모든 자연수가 4 이하의 제곱합으로 표현될 수 있음을 증명했습니다.
일부 자연수는 복수로 표현됩니다.
예를 들어 26은 52와 12의 합입니다.
또한 42 + 32 + 1

'추천 관련글,

www.acmicpc.net

문제

라그랑주는 1770년에 모든 자연수가 4 이하의 제곱합으로 표현될 수 있음을 증명했습니다.
일부 자연수는 복수로 표현됩니다.
예를 들어, 26은 $5^2$와 $1^2$의 합입니다.
또한 $4^2$ + $3^2$ + $1^2$로도 표현할 수 있습니다.
역사적으로 암산 마스터의 일반적인 문제는 자연수를 4 이하의 제곱의 합으로 표현하는 것이었습니다.
20세기 초의 수석 수학자는 15663 = $125^2$ + $6^2$라고 계산했습니다.
+ $1^2$ + $1^2$의 답을 찾는 데 8초가 걸렸다는 보고가 있습니다.
더 어려운 작업은 56초가 걸렸습니다: 11339 = $105^2$ + $15^2$ + $8^2$ + $5^2$.

자연수 n이 주어지면, n을 가장 작은 수의 제곱의 합으로 표현하는 컴퓨터 프로그램을 작성하십시오.

기입

입력에는 표준 입력이 사용됩니다.
입력값은 자연수입니다.
N1 ≤인 단일 행으로 구성됩니다.
N ≤ 50,000.

누르다

출력은 표준 출력을 사용합니다.
총 N한 줄에 동일한 최소 사각형 수를 인쇄하십시오.

728×90

예시 입력 1

25

예제 출력 1

1

샘플 입력 2

26

샘플 출력 2

2

샘플 입력 3

11339

샘플 출력 3

3

샘플 입력 4

34567

예제 출력 4

4
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {

	public static void main(String() args) throws Exception {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		
		int() dp = new int(n + 1);
		Arrays.fill(dp, Integer.MAX_VALUE);
		
		dp(0) = 0;
		for (int i = 0; i < n; i++) {
			int j = 1;
			while(i + Math.pow(j, 2) <= n) {
				int tmp = (int) (i + Math.pow(j, 2));
				dp(tmp) = Math.min(dp(tmp), dp(i) + 1);
				j++;
			}
		}
		
		System.out.println(dp(n));
	}

}