main
[백준-1699번/Java] 제곱수의 합 본문
* DP ; 동적 계획법
* 1부터 N 범위까지
- case1 : 가장 큰 제곱수 부터 빼는 연산, 전체 연산 횟수를 count에 저장
- case2 : 1 <= j < (i 의 제곱근) 범위의 의 dp[i - (j * j)] + 1해서 case1보다 작은 값이 있다면 저장
* 가장 큰 제곱수 부터 빼는 방식으로 해결 안됨.
반례) 753
3 (625 + 64 + 64 = 753)
import java.io.*;
import java.util.*;
public class Main {
static private int largestSquareRoot(int num) {
return (int) Math.sqrt(num);
}
public static void main(String[] args) throws IOException {
Scanner in = new Scanner(System.in);
int N = in.nextInt();
int[] dp = new int[N + 1];
for (int i = 1; i < dp.length; i++) {
int count = 0;
int num = i;
while (num > 0) {
num -= Math.pow(largestSquareRoot(num), 2);
count++;
}
for (int j = 1; j < largestSquareRoot(i); j++) {
count = Math.min(dp[i - (int) Math.pow(j, 2)] + 1, count);
}
dp[i] = count;
}
System.out.println(dp[N]);
}
}
728x90
'Algorithm' 카테고리의 다른 글
[백준-17219번/Java] 비밀번호 찾기 (0) | 2022.11.16 |
---|---|
[백준-1932번/Java] 정수 삼각형 (0) | 2022.11.16 |
[인프런/Java] 특정 문자 뒤집기 (0) | 2022.11.15 |
[백준-1463번/Java] 1로 만들기 (0) | 2022.11.15 |
[백준-10814번] 나이순 정렬 (0) | 2022.11.15 |