-
[알고리즘-JAVA]백준 알고리즘 1699번 - 제곱수의 합알고리즘 2019. 8. 22. 19:56
접근 과정
1. 어떤 문제로 이해 했는가? 그리고 문제의 제약 조건은?주어진 자연수를 제곱수의 합으로 나타낼때 그 제곱수 항의 최소 개수 구하기
2. 나의 방식대로 문제를 재정의 하자.d[i] = 제곱수 합의 최소 개수
3. 어떤 알고리즘과 자료구조를 사용할 것인가?bottom-up을 이용한 dp
4. 어떻게 계산할 것인가?
1) 입력Scanner사용
2) 시간 복잡도 계산
n만큼의 d배열을 채우면서, 1<=i<=루트N인 연산을 해야하므로
O(N루트N)이다.
5. 주의할 점은 무엇인가?6. 풀이 과정
마지막에 들어갈 수 있는 수는 특정 i의 제곱수이므로
항의 개수는 1개가 늘어나게 된다. 이때 n - i^2중에서 가장 최소에다가 1을 더해주면 된다.
d[n] = min(d[n - i^2] + 1)
만약, 최소개수가 아닌 전체 가능한 가짓수를 구하라고 하면
d[n] = sum(d[n - i^2])을 구하면 된다.
[전체 소스 코드]
import java.util.Scanner; import java.lang.Math; public class Main { public static int d[]; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int number = sc.nextInt(); d = new int[number+1]; //d[n] = min(d[n - i^2] + 1) for (int i = 1; i <= number; i++){ d[i] = i; for (int j = 1; j*j <= i; j++){ if (d[i] > d[i-j*j]+1){ d[i] = d[i-j*j]+1; } } } System.out.println(d[number]); } }
'알고리즘' 카테고리의 다른 글
[알고리즘-JAVA] 백준 알고리즘 2579번 - 계단 오르기 (0) 2019.08.16 [알고리즘-JAVA] 백준 알고리즘 1912번 - 연속합 (0) 2019.08.15 [알고리즘-JAVA] 백준 알고리즘 11053번 - 가장 긴 증가하는 부분수열 (0) 2019.08.15 [알고리즘-JAVA] 백준 알고리즘 2156번 - 포도주 시식 (0) 2019.08.15 [알고리즘-JAVA] 머지소트(Merge Sort)구현 (0) 2019.08.11