입력은 표준입력을 사용한다. 입력은 자연수 n을 포함하는 한 줄로 구성된다. 여기서, 1 ≤ n ≤ 50,000이다.
출력은 표준출력을 사용한다. 합이 n과 같게 되는 제곱수들의 최소 개수를 한 줄에 출력한다.
dp로 푸는 문제
저번달에 푼지 모르고 한번 더 풀었는데
전체적인 흐름은 같지만 내가 보기엔
2번 방식이 좀 더 정석적인거 같다..?
메모리나 속도적인 면에서 조금 더 우수하다
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] dp = new int[n + 1];
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]);
}
}
import java.util.Scanner;
public class Main {
static int[] dp;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
dp = new int[50001];
for (int i = 1; i * i <= n; i++) {
dp[i*i] = 1;
}
for (int i = 1; i <= n; i++) {
if(dp[i]!= 0) continue;
makeDp(i);
}
System.out.println(dp[n]);
}
static void makeDp(int num) {
for (int i = 1; i * i <= num; i++) {
if(dp[num] == 0)
dp[num] = dp[i * i] + dp[num - i * i];
else dp[num] = Math.min(dp[num], dp[i * i] + dp[num - i * i]);
}
}
}