박시은

(❁´◡`❁)

4 분 소요


https://www.acmicpc.net/problem/17626


📌 문제

문제 유형

  • DP


문제 설명

  • 어떤 자연수는 네 개 이하의 제곱수의 합으로 표현할 수 있다.
  • 예를 들어 26은 5² + 1² 또는 4² + 3² + 1²로 표현 가능.
  • 주어진 수 n을 제곱수의 합으로 표현할 때, 제일 적은 개수를 출력하라.


입출력 예시

  • 입력

    • 입력은 표준입력을 사용한다. 입력은 자연수 n을 포함하는 한 줄로 구성된다. 여기서, 1 ≤ n ≤ 50,000이다.

      26

  • 출력

    • 출력은 표준출력을 사용한다. 합이 n과 같게 되는 제곱수들의 최소 개수를 한 줄에 출력한다.

      2



🔍 문제 풀이

① dp 배열의 의미

  • dp[i]는 숫자 i를 제곱수의 합으로 표현할 때의 최소 개수를 저장


② 점화식

규칙을 찾아보자

1 = 1^2                              → 최소 개수: 1
2 = 1^2 + 1^2                        → 최소 개수: 2
3 = 1^2 + 1^2 + 1^2                  → 최소 개수: 3
4 = 2^2                              → 최소 개수: 1
5 = 2^2 + 1^2                        → 최소 개수: 2
6 = 2^2 + 1^2 + 1^2                  → 최소 개수: 3
7 = 2^2 + 1^2 + 1^2 + 1^2            → 최소 개수: 4
8 = 2^2 + 2^2                        → 최소 개수: 2


dp 값 계산 흐름

dp[1] = 1                    // 1 = 1^2
dp[2] = dp[1] + 1 = 2        // 2 = 1^2 + 1^2
dp[3] = dp[2] + 1 = 3        // 3 = 1^2 + 1^2 + 1^2
dp[4] = 1                    // 4 = 2^2
dp[5] = dp[1] + 1 = 2        // 4 + 1 = 2^2 + 1^2
dp[6] = dp[2] + 1 = 3        // 4 + 1 + 1
dp[7] = dp[3] + 1 = 4        // 4 + 1 + 1 + 1
dp[8] = dp[4] + 1 = 2        // 4 + 4
dp[9] = 1                    // 9 = 3^2
dp[10] = dp[1] + 1 = 2       // 9 + 1
dp[11] = dp[2] + 1 = 3       // 9 + 1 + 1
dp[12] = dp[8] + 1 = 3       // 4 + 4 + 4
dp[13] = dp[4] + 1 = 2       // 9 + 4
dp[14] = dp[13] + 1 = 3      // 9 + 4 + 1
dp[15] = dp[14] + 1 = 4      // 9 + 4 + 1 + 1
dp[16] = 1                   // 16 = 4^2

제곱수(i = j²)인 경우, 해당 수 하나로만 표현 가능하므로 dp[i] = 1이 된다.

이후의 수들은 제곱수 + 나머지의 형태로 구성되며, dp값이 점점 커지다가,

다음 제곱수를 만날 때 다시 dp 값이 1로 초기화되는 것을 확인할 수 있다.


따라서, 점화식은 아래와 같다.

dp[i] = min(dp[i], dp[i - j*j] + 1) // 제곱 수 dp[j*j] , 나머지 합 dp[i-j*j]
  • 가능한 모든 제곱수 j*j ≤ i에 대해 반복하면서 가장 적은 제곱수 개수 조합을 찾는다.

  • j*j는 i보다 작거나 같은 제곱수를 의미한다.

  • 1+ 의미
    • dp[i - j*j]는 남은 수를 만드는 최소 개수
    • +1 은 지금 내가 사용한 j*j 하나를 뜻함
    • 이걸 누적해가면서 최소 개수를 찾는 게 핵심


③ 초기화

  • dp[0] = 0, 나머지는 순차적으로 계산
  • 각 dp[i]는 처음에 Integer.MAX_VALUE로 설정해두고 비교 시작


예시

  • dp[12]를 구할 때 가능한 제곱수는:
    • 1² = 1
    • 2² = 4
    • 3² = 9


dp[12] = min(
    dp[11] + 1 = 4 + 1 = 5,
    dp[8]  + 1 = 2 + 1 = 3,
    dp[3]  + 1 = 3 + 1 = 4
) = 3

즉, dp[12]를 구할 때 가능한 제곱수 j² = 4를 사용했다고 가정하면:

  • 12 = 4 + 남은 8
  • 8을 만드는 최소 개수는 dp[8] = 2
  • 거기다가 내가 지금 4(=2²) 하나를 썼으니까 +1

→ 그래서 이 조합의 총 개수는 2 + 1 = 3



📌 배운 점

규칙을 찾기 정말 힘들었던 문제이다.

처음에는 단순히 1²을 여러 번 더해서 누적하면 된다고 생각했지만, 실제로는 모든 제곱수를 조합해서 최소 개수를 선택하는 방식이었다.


+1은 선택한 제곱수 하나를 의미한다는 점도 이해하는 데 시간이 걸렸고, dp[i - j*j] + 1을 통해 남은 수에 대한 최소값을 재활용한다는 점도 헷갈렸다.


특히 dp[12] = min(dp[11] + 1, dp[8] + 1, dp[3] + 1) 같은 계산을 통해, 이전 값들에 기반해 최적해를 선택하는 구조를 직접 확인하며 많은 도움이 되었다.


앞으로 DP 문제를 풀 때 구조를 직접 손으로 써보고,
“현재 값이 이전 값들을 어떻게 재사용하는가” 를 먼저 파악해야겠다.

힘들었ㄷ.ㅏ..



💻 전체 코드

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        int[] dp = new int[50001];
        dp[0] = 0;
        dp[1] = 1;

        for(int i=2; i<=n; i++){
            dp[i] = Integer.MAX_VALUE;
            for(int j=1; j * j<=i; j++){
                dp[i] = Math.min(dp[i], dp[i - j * j]  + 1);

            }
        }
        System.out.println(dp[n]);
    }
}



🤖 점화식 뜯어보기

점화식은 아래와 같다. dp[12]를 찾아보자

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


왜 2의 제곱(2^2 = 4)을 씀?

  • 2² = 4는 12보다 작거나 같은 제곱수이기 때문
  • 즉, “12를 만들기 위해 4를 먼저 사용하고, 남은 8을 어떻게 만들까?”를 생각함

왜 3의 제곱(3² = 9)을 안 씀?

  • 사실 3² = 9도 고려 대상
  • 다만 dp[12]를 구할 땐 가능한 모든 제곱수를 다 비교한 후,그 중 가장 작은 값을 선택한다.
  • 예를 들면:
    • dp[3] + 1 = 3 + 1 = 4
    • dp[8] + 1 = 2 + 1 = 3 ← 더 작으므로 선택됨

→ 따라서 “3의 제곱을 안 쓴 게 아니라, 썼지만 최소가 아니었기 때문에 탈락된 것”임.

왜 dp[8]을 참고함?

  • 12 - 4 = 8이 남았고,
  • 8을 만드는 최소 제곱수 개수는 이미 dp[8]에 저장되어 있기 때문

왜 +1을 더함?

  • 지금 2² = 4 하나를 사용했으므로 제곱수 1개 추가


⇒ dp[8] + 1 = 2 + 1 = 3
⇒ 12를 만들기 위한 조합 중 하나로 3개가 들었음.
(다른 j²들도 다 비교해보고 이 값이 최소라면 dp[12]가 됨)


카테고리:

업데이트:

댓글남기기

참고