b1699. 제곱수의 합

 

 

✨ 자바로 푸는 제곱수의 합 문제 풀이

 

---

 

📌 문제 개요

 

숫자 N이 주어졌을 때,

N을 제곱수들의 합으로 표현하는 최소 항의 수를 구하는 문제입니다.

 

예를 들어 11 = 3² + 1² + 1² → 3개

가능한 조합 중에서 가장 적은 수의 항으로 표현해야 합니다.

 

---

 

💡 예제 입력

11

 

💡 예제 출력

3

 

---

 

🛠 알고리즘 접근 방식

 

이 문제는 **DP(동적 계획법)**을 활용하여,

N 이하의 제곱수들을 조합해서 가장 적은 개수로 N을 만드는 방법을 찾는 방식입니다.

 

 

🔸 점화식

 

dp[i] = min(dp[i - j*j] + 1)

(단, j*j ≤ i인 모든 j에 대해)

 

즉, i에서 가능한 모든 제곱수(j²)를 뺀 후,

그 나머지를 만드는 최소 개수(dp[i - j*j])에 1을 더해 최소를 구합니다.

 

---

 

✅ 핵심 아이디어

 

• dp[i]는 숫자 i를 제곱수 합으로 표현할 때 최소 항의 수
• 가능한 제곱수들을 순회하며 i - j^2을 통해 이전 상태로 이동
• 메모이제이션을 활용한 탑다운 방식 구현

 

---

 

🧾 코드 해설

dp = new int[N+1];
Arrays.fill(dp, Integer.MAX_VALUE);
dp[0] = 0;

 

• 초기값 세팅: 최소 항의 수를 구하므로 최댓값으로 초기화

for (int i = 1; i <= N; i++) {
    dp[i] = dp[logic(i)] + 1;
}

 

• 현재 숫자를 만들 수 있는 가장 가까운 제곱수 하나를 구해
• 그걸 뺀 나머지를 구한 뒤 +1

private static int logic(int n) {
    if (dp[n] != Integer.MAX_VALUE) return dp[n];
    int answer = Integer.MAX_VALUE;
    for (int i = 1; Math.pow(i, 2) <= n; i++) {
        answer = Math.min(answer, logic(n - (int)Math.pow(i, 2)));
    }
    return answer;
}

 

• 가능한 모든 제곱수 i에 대해 n - i² 재귀 호출
• dp[n] 메모이제이션 활용으로 중복 호출 최소화

 

---

 

✅ 핵심 포인트 정리

 

• 제곱수는 1, 4, 9, 16, ... 등으로 한정적이므로 완전탐색이 가능
• dp[i] = min(dp[i - j*j] + 1) 로 점화식을 설정
• 메모이제이션으로 성능 최적화

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

import static java.lang.Math.pow;

public class Main {

    static int N;
    static int[] dp;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        dp = new int[N+1];
        Arrays.fill(dp,Integer.MAX_VALUE);
        dp[0] = 0;
        for(int i = 1 ; i <= N ; i++){
            dp[i] = dp[logic(i)]+1;
        }
        System.out.println(dp[N]);
    }
    private static int logic(int n){
        if(dp[n] != Integer.MAX_VALUE) return dp[n];
        int answer = Integer.MAX_VALUE;
        for(int i = 1 ; Math.pow(i,2) <= n ; i++){
            answer = Math.min(answer,logic((int)(n-Math.pow(i,2))));
        }
        return answer;
    }
}