BOJ01699 제곱수의 합

https://www.acmicpc.net/problem/1699 (opens new window)

어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=3²+1²+1²(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=2²+2²+1²+1²+1²(5개 항)도 가능하다. 이 경우, 수학자 숌크라테스는 “11은 3개 항의 제곱수 합으로 표현할 수 있다.”라고 말한다. 또한 11은 그보다 적은 항의 제곱수 합으로 표현할 수 없으므로, 11을 그 합으로써 표현할 수 있는 제곱수 항의 최소 개수는 3이다.

주어진 자연수 N을 제곱수들의 합으로 표현할 때 그 항의 최소 개수를 구한다.

다이나믹 프로그래밍

n	제곱수 표현	항의 개수 최솟값
1	11	1
2	11 + 11	2
3	11 + 11 + 11	3
4	22	1
5	22 + 12	2
6	22 + 12 + 12	3
7	22 + 12 + 12 + 12	4
8	22 + 22	2

항의 개수 최솟값을 구하기 위해서는 크게 두가지 포인트를 가지고 있다.

1. n이 8인 경우 dp[8] = dp[4] + dp[4]로 표현이 가능하다. 즉 아래 식 중 가장 작은 항의 개수를 가진다. 모든 경우 아래 상황을 만족한다.

dp[n] = dp[1] + dp[n - 1]
      = dp[2] + dp[n - 2]
      = ...
      = dp[n / 2] + dp[n / 2]

2. n이 제곱수로 표현이 가능한 경우 최솟값은 1이된다. n이 4라고 가정하면 2²로 표현 가능하기 때문이다.

제출 코드

아래는 최종 제출 코드이다.

import java.util.Scanner;

public class BOJ1699 {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();
        int[] dp = new int[n + 1];

        for (int i = 1; i <= n; i++) {
            dp[i] = i;
            for (int j = 1; j <= i / 2; j++) {
                if (j * j == i) { // 제곱수 표현이 가능한 경우
                    dp[i] = 1;
                    break;
                }

                // 모든 경우를 순회하며 최솟값 저장
                dp[i] = Math.min(dp[i], dp[i - j] + dp[j]); 
            }
        }

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

#BOJ #수학 #다이나믹 프로그래밍 #정수론