https://www.acmicpc.net/problem/17626
17626번: Four Squares
라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 1
www.acmicpc.net
저는 DP를 이용하여 문제를 해결하였습니다.
DP를 이용해 이전에 계산한 값을 다시 계산하지 않도록 하였습니다.
숫자가 해당 숫자의 제곱근의 제곱과 같은지를 확인하고 같다면 1을 리턴하고 같지 않다면 제곱근부터 1까지 줄여나가면서 숫자를 줄여나가면서 계산하였습니다.
package BOJ.dp;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.function.Function;
public class BOJ_17626 {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
Function<String,Integer> stoi = Integer::parseInt;
int n = stoi.apply(br.readLine());
int[] dp = new int[n+1];
int result = cal(n,dp);
System.out.println(result);
}
private static final int INF = 987654321;
private static final int NOT_VALID = 0;
private static int cal(int n, int[] dp) {
if(dp[n] != NOT_VALID){
return dp[n];
}
int result = INF;
for(int i = (int)Math.sqrt(n) ; i >= 1 ; i--){
if(n == i * i){
return 1;
}else{
result = Math.min(result,cal(n - i*i, dp)+1);
}
}
dp[n] = result;
return result;
}
}
'알고리즘' 카테고리의 다른 글
프로그래머스 코딩 테스트 공부 (JAVA) (0) | 2022.09.05 |
---|---|
프로그래머스 문자열 다루기 (JAVA) (0) | 2022.09.04 |
프로그래머스 두 큐 합 같게 만들기 (JAVA) (0) | 2022.09.02 |
프로그래머스 성격 유형 검사하기(JAVA) (0) | 2022.09.01 |
백준 5972번 택배 배송 (JAVA) (0) | 2022.08.31 |