[백준-17626] Four Squares

공부/백준

빈v 2022. 7. 14. 20:15

728x90

17626번: Four Squares

라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 1

www.acmicpc.net

백준 17626번 Four Squares 자바 풀이

난이도: 실버3

코드

import java.util.*;

public class back17626 {

public static void main(String args[]){

Scanner scanner = new Scanner(System.in);

int n=scanner.nextInt();

int []dp=new int[50001];

dp[0]=0;

dp[1]=1;

for(int i=2;i<=n;i++){

int min=Integer.MAX_VALUE;

for(int j=1;j*j<=i;j++){

min=Math.min(min,dp[i-j*j]);

}

dp[i]=min+1;

}

System.out.println(dp[n]);

}

728x90