[Java] BOJ 1699번 제곱수의 합

1699번: 제곱수의 합

---

풀이

최대 항의 최대 개수는 1^2으로만 이루어진 경우이므로 memo[i] = i로 초기화하였습니다.

i - (j ^ 2)인 수의 최대항의 개수 + 1중 최소인 값을 찾아 해결했습니다.

예를 들어 i = 5, j = 2라면 5 - (2 ^ 2) = 1이므로 memo[1]의 최대 항의 최소 개수는 1입니다. 때문에, 1 + (2 ^ 2)를 하면 원래 i인 5가 되므로 문제에서 요구한 제곱수의 합으로 표현되므로 memo[1] + 1을 한 값이 i = 5일 때의 최대 항의 개수 중 하나가 됩니다. 최소를 구하기 위해서는 j * j <= i가 될 때까지 반복하며 비교해야 합니다.

---

코드

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

public class Main {
	public static int N;
	public static int[] memo = new int[100001];
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		N = Integer.parseInt(br.readLine());
		
		for (int i = 1; i <= N; ++i) {
			// 최대의 항의 개수는 1^2 으로만 이루어진 경우이므로
			// 현재 숫자가 된다.
			memo[i] = i;
			
			// j^2이 i보다 작다면 i - (j ^ 2)를 한 수에서 j ^ 2 즉, 제곱수를 하나만 더 추가하면 된다.
			// 때문에 i - (j * j) 번째 까지의 최대 항의 개수 + 1을 한 값이 현재 저장된 최대항의 개수보다 작다면
			// 갱신되게 해야한다.
			for (int j = 1; j * j <= i; ++j) {
				if (memo[i] > memo[i - (j * j)] + 1) {
					memo[i] = memo[i - (j * j)] + 1;
				}
			}
		}
		
		System.out.println(memo[N]);
	}
}

---

pyo7410/Algorithm