문제
라그랑주의 네 제곱수 정리에 의해 모든 자연수는 최대 4개의 제곱수 합으로 표현할 수 있다. 주어진 N을 제곱수 합으로 나타낼 때 최소 항의 개수를 구하라.
입력
첫째 줄에 N (1 이상 50,000 이하)이 주어진다.
출력
N을 제곱수 합으로 표현할 때 최소 항 수를 출력한다.
예제
| 입력 | 출력 |
|---|---|
25 | 1 |
풀이
DP로 각 수를 제곱수 합으로 나타내는 최소 항 수를 구한다.
dp[i]를 i를 제곱수 합으로 표현하는 최소 항 수로 정의한다- 2부터 N까지, j를 1부터
j*j <= i인 동안 반복한다 dp[i] = min(dp[i - j*j]) + 1로 갱신한다 (j²를 하나 사용)dp[N]을 출력한다
핵심 아이디어: 동전 교환 문제와 동일한 구조. 사용 가능한 "동전"이 1², 2², 3², ...인 최소 개수 문제로, 내부 루프가 sqrt(i)까지만 돌므로 O(N*sqrt(N))이다.
코드
import java.io.*;
public class Day365BOJ176264스퀘어 {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int N = Integer.parseInt(br.readLine());
int[] dp = new int[N + 1];
dp[1] = 1;
int min = 0;
for (int i = 2; i <= N; i++) {
min = Integer.MAX_VALUE;
for (int j = 1; j * j <= i; j++) {
int temp = i - j * j;
min = Math.min(min, dp[temp]);
}
dp[i] = min + 1;
}
bw.write(dp[N] + "\n");
bw.flush();
bw.close();
br.close();
}
}복잡도
- 시간: O(N * sqrt(N)) - 각 i마다 sqrt(i)개의 제곱수 확인
- 공간: O(N)