50000 숫자를 입력받았다면 제곱근은 1~223 이므로 대략 200 * 50000 은 1000만이다 이것도 많이 잡은수치이다 왜냐면 50000 보다 작은 숫자는 제곱근 개수가 적으므로 계산량이 적어서
실제 코드로 찍어본 시간복잡도 7478797
https://www.acmicpc.net/problem/17626
단순for문으로 푸는건 실패 하였다;;
for문 돌리면서 숫자 n을 sqrt 하고 나온숫자를 카운트해서 min 변수에 최소값을 갱신하면 되지 않을까 했는데 안된다
import java.io.*;
import java.util.*;
public class Main {
static int n;
static double ncopy;
static ArrayList<Integer> answer;
static int change;
static final int maxsqrt = 4;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
ncopy = n;
answer = new ArrayList<>();
change = 0;
int temp = 2;
int min = Integer.MAX_VALUE;
while(true)
{
temp = (int)Math.sqrt(ncopy);
if(answer.isEmpty())
{
temp -= change;
}
ncopy -= Math.pow(temp, 2);
answer.add(temp);
if(answer.size() > maxsqrt)
{
Init();
}
else if(ncopy == 0)
{
min = Math.min(min, answer.size());
Init();
}
if( (answer.size()>2) && (answer.get(0) < answer.get(1)) )
break;
}
System.out.println(min);
}
static void Init()
{
answer.clear();
ncopy = n;
change++;
}
}그래서 인터넷을 보고 풀이를 봐도 이해가 잘되지 않아서 한참을 찾아보고 찾아봤다
대충 어느정도 이해가 되는것 같다 이런 규칙을 나도 찾아낼 수 있을까 싶다
동적계획법(해를 구하고 재활용해서 새로운 해를 구해나가는 방식)으로 푸는 방법이다
dp[i] 라는 배열을 만들고 i를 구하는 제곱수의 최소개수를 dp[i]의 값으로 넣는다. 그리고 dp[i+1] 은 이전에 구해놨던 dp배열의 값을 이용해서 푸는 것이다.
dp[i] = dp[i-j*j] + 1
일단 공식을 봤는데 공식이 이해가 안되어서 dp배열을 직접 일일이 계산해 보았다
dp[0] = 0
dp[1] = 1 (dp[1] = 1^2)
dp[2] = 2 (dp[1] + dp[1] = 1^2+1^2)
dp[3] = 3 (dp[1] + dp[1] + dp[1] = 1^2+1^2+1^2)
dp[4] = 1 (dp[4], 2^2)
(2^2) or (1^2 + 1^2 + 1^2 + 1^2) 둘중에 작은개수는 (2^2)
dp[5] = 2 (dp[4] + dp[1] = 2^2 + 1^2)
(2^2 + 1^2) + (1^2 or 1^2 + 1^2 + 1^2 + 1^2 + 1^2) 둘중에 작은개수는 (2^2 + 1^2)
dp[6] = 3 (dp[4] + dp[1] + dp[1] = 2^2 + 1^2 + 1^2)
dp[7] = 4 (dp[4] + dp[1] + dp[1] + dp[1] = 2^2 + 1^2 + 1^2 + 1^2)
dp[8] = 2 (dp[4] + dp[4] = 2^2 + 2^2)
dp[9] = 1 (dp[9] = 3^3)
dp[10] = 2 (dp[9] + dp[1] = 3^3 + 1^2)
dp[11] = 3 (dp[9] + dp[1] + dp[1] = 3^3 + 1^2 + 1^2)
그래도 잘이해가 되지 않았다. 왜 저렇게 공식이 나왔는지 한참을 찾아보고 고민하고 겨우 이해할 수 있었다.
제곱수를 만들기 위한 최소 제곱수의 개수는 항상 1이다. 예를들어 dp[4] = 1 이다. 4는 제곱수2^2 로 만들 수 있으니까. 따라서 dp[제곱수] = 1 이다.
dp[0] = 0 이다. 0을 만들 수 있는 제곱수는 없으니까
dp[1] = 1 이다. 1을 만들기위한 제곱수는 1^2 하나니까
이제 dp[2] 를 구해보자. 2를 sqrt(제곱근구하는함수) 하고 int 로 받으면 1이다. 따라서 2를 만들기 위한 제곱수중 가장큰 수는 1이다. (그리고 2를 만들기 위한 제곱수는 1 하나밖에 없다) 숫자 1 을 만들기 위한 최소제곱수는 dp[1] 에 있다. 따라서
dp[2] = dp[2] - dp[1] + dp[1] 로 표현할 수 있다.
dp[2] = dp[1] + dp[1] 이므로 dp[2] = 2 이다. dp[2] 를 구하기 위해 dp[1]을 재활용 하였다.
n 을 12 라고 가정해보자 dp[12] 를 구하기위해 사용가능한 제곱수(1, 4, 9) 부터 구한다.
Math.sqrt(12) 를 하면 3이 나온다. 1,2,3 은 12를 만들기위한 제곱수들중에 포함되는 완전제곱수의 제곱근 이다. 제곱근을 제곱하면 1^2, 2^2, 3^3 => 1, 4, 9 은 12를 만들기위한 제곱수들중에 포함되는 완전제곱수 이다.
1, 4, 9 완전제곱수 들은 각자 자기자신을 만들기 위한 제곱수가 1개만 필요하다. 1=>1, 2=>4, 3=>9.
dp라는 int 배열을 만들고 배열의 값에 배열인덱스를 구하기 위한 필요한 최소개의 제곱수의 개수를 저장한다고 생각해보자. 그렇다면 다음과 같다 dp[1] = 1, dp[4] = 1, dp[9] = 1
12를 만들기 위해 1, 4, 9를 사용할 수 있다고 하였다. 이를 dp로 표현해보자
dp[12] = dp[1] + dp[11]
dp[12] = dp[4] + dp[8]
dp[12] = dp[9] + dp[3]
dp[12] = 1 + dp[11]
dp[12] = 1 + dp[8]
dp[12] = 1 + dp[3]
dp[12] = 1 + dp[11] = 1 + 3
dp[12] = 1 + dp[8] = 1 + 2
dp[12] = 1 + dp[3] = 1 + 3
가장 작은수는 3 따라서 dp[12] = 3
dp[12]를 구하기 위해 이전에 구해놨던 dp[11], dp[8], dp[3] 을 재활용하는것을 볼 수 있다
재활용하기 위한 코드를 만들어 보자
dp[12] = dp[12] - dp[1] + dp[1]
dp[12] = dp[12] - dp[4] + dp[4]
dp[12] = dp[12] - dp[9] + dp[9]
dp[12] = dp[11] + 1
dp[12] = dp[8] + 1
dp[12] = dp[3] + 1
이것을 코드로 변환하면 다음과 같다
j 는 i를 만들 수 있는 제곱근들중 하나이다.
dp[i] = dp[i-j*j] + 1
코드를 다시 풀어서 써보면 다음과 같다
dp[12] = dp[12- 1*1] +1
dp[12] = dp[12] - dp[1] + dp[1]
dp[12] = dp[11] + dp[1]
dp[12] = dp[12- 2*2] +1
dp[12] = dp[12] - dp[4] + dp[4]
dp[12] = dp[8] + dp[4]
dp[12] = dp[12- 3*3] +1
dp[12] = dp[3] + dp[9]
import java.io.*;
import java.util.*;
public class Main {
static int n;
static double ncopy;
static ArrayList<Integer> answer;
static int change;
static final int maxsqrt = 4;
static int[] dp = new int[50001];
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
int min = Integer.MAX_VALUE;
for(int i = 0; i < dp.length; ++i)
{
dp[i] = 4;
}
dp[0] = 0;
dp[1] = 1;
dp[2] = 2;
dp[3] = 3;
int squareNumber;
for(int i = 4; i <= n; ++i)
{
min = Integer.MAX_VALUE;
squareNumber = (int)Math.sqrt(i);
for(int j = 1; j <= squareNumber; ++j)
{
min = dp[i-j*j]+1;
dp[i] = Math.min(dp[i], min);
}
}
System.out.println(dp[n]);
}
}