JAVA_LeetCode 279_Perfect Squares 풀이 class Solution { public int numSquares(int n) { // dp[i]는 i를 완전제곱수의 합으로 만드는 최소 개수를 저장 int[] dp = new int[n + 1]; Arrays.fill(dp, Integer.MAX_VALUE); dp[0] = 0; // 0은 0개의 제곱수로 표현 가능 // 점화식 : 현재 숫자 i에서 가능한 완전 제곱수(j⑵)를 빼고 남은 수의 최솟값에 1을 더하여 최소값을 구하는 방식 for(int i = 1; i <= n; i++){ for(int j = 1; j * j <= i; j++) dp[i] = Math.min(dp[i], dp[i - j * j] + 1); } return dp[n]; } } dp, 점화식 풀이 n을 완전 제곱수(예: 1, 4, 9, 16, ...)의 합으로 표현할 때, 최소 몇 개의 완전 제곱수가 필요한가에 대한 문제 dp[i]를 ...
