[백준 실버 2] 1699번: 제곱수의 합

문제

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

1699번: 제곱수의 합

 

 

풀이

• 자연수 N을 제곱수의 합으로 표현해야 한다. 예를 들어 5 = 1^2 + 2^2, 즉 2개의 항으로 나타낼 수 있다.
• 이때 N을 제곱수의 합으로 나타낼 때, 최소 항의 개수를 구한다.
• 모든 자연수 N의 최대 항의 개수는 N개이다. 1^2의 합으로 표현할 수 있기 때문이다.
• 제곱수 N의 최소 항의 개수는 무조건 1개이다. 제곱해서 N이 되는 수 하나만 존재하는 경우가 이에 해당한다.
• N의 범위는 1 이상 100,000 이하이다.

N의 값이 최대 100,000이기 때문에 위 성질을 이용해 점화식을 만들어 풀어야 한다.

정수형 배열 dp를 선언한다. 이때 dp[i]는 자연수 i를 제곱수의 합으로 나타낼 때 최소 항의 개수이다.

비교하기 전 dp[i]의 초기값은 i로 선언할 수 있다. 모든 자연수 N의 최대 항의 개수는 N개이기 때문이다.

int dp[] = new int[N + 1];

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

	// ...
}

 

항의 개수를 줄이기 위해서는 제곱수가 필요하다. 즉, dp[i]를 구하기 위해서는 i보다 작은 제곱수를 알 필요가 있다.

예를 들어 N = 12이라면, 12보다 작은 제곱수는 1, 4, 9가 있다.

dp[12]는 dp[12 - 1], dp[12 - 4], dp[12 - 9] 중에서 제일 작은 값에 1을 더한 것이다. dp[i]는 이미 최소 항의 개수이므로 자연스럽게 dp[12]는 위 세 경우 중 최소값에서 1을 더하면 된다.

for (int j = 1; j * j <= i; j++) {
    if (dp[i] > dp[i - j * j] + 1) {
        dp[i] = dp[i - j * j] + 1;
    }
}

 

 

전체 코드 (Java)

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int dp[] = new int[N + 1];

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

			for (int j = 1; j * j <= i; j++) {
				if (dp[i] > dp[i - j * j] + 1) {
					dp[i] = dp[i - j * j] + 1;
				}
			}
		}
		System.out.println(dp[N]);
	}
}

 

 

후기

다이나믹 프로그래밍 문제는 풀 때마다 새롭다. 다른 문제들과 성격이 약간 다른 만큼 꾸준히 풀어서 까먹지 않도록 해야겠다.