자연수 n이 주어지고 제곱수 들의 합으로 n을 표현할 때, 필요한 제곱수 개수의 최솟값을 구하는 문제.
아이디어
처음에는 브루트포스로 풀어야 겠다고 다짐하고 모든 제곱수를 저장한 후, 가장 n에 근사한 값 부터 나누기 및 빼기를 통해 최솟값을 찾았다.
50%까진 통과했지만, 그 이후로 계속 실패해서 결국 다른 사람의 풀이를 읽었다.
내가 구현했던 브루트포스 풀이는 잘못된 풀이로, 모든 조합을 고려하지 못했기 때문에 틀렸다는 결론이 났다(근데 반례는 못찾았다...)
DP의 bottom-up 방식으로 접근한다.
첫 번째 for 문에서 1부터 n까지 올라가며 각 제곱수를 구하고,
두 번째 for 문에서 첫 번째 for 문의 i * i 를 사용해 dp 배열을 업데이트한다.
이 때, dp[j] 는 현재 제곱수 i * i 를 사용해 j 를 표현할 수 있는 아래 두 경우 중 최솟값으로 갱신한다.
'j - (i * i) 를 만드는 데 필요한 최소 횟수' + 'i * i 를 추가로 더해 j 를 표현하는 경우' = dp[j - i * i] + 1
기존에 저장된 횟수 = dp[j]
이 과정을 마치면, dp[n] 에는 n 을 제곱수의 합으로 표현할 때 필요한 제곱수의 최소 개수가 저장되어 있다.
풀이
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int[] dp = new int[n+1];
// 최솟값 갱신을 위해 모든 값을 큰 수로 초기화
Arrays.fill(dp, Integer.MAX_VALUE);
// 0은 0번 취급
dp[0] = 0;
for(int i=1; i*i<n+1; i++) {
// j를 만드는데 필요한 최소 연산을 갱신함
for(int j=i*i; j<n+1; j++) {
dp[j] = Math.min(dp[j], dp[j-i*i] + 1);
}
}
System.out.println(dp[n]);
}
}
