[Baekjoon] 1699_제곱수의 합

문제(출처: https://www.acmicpc.net/problem/1699)

---

< 제곱수의 합 >

 

문제 풀이 

 

예를 들어 5를 만들기 위해서는 2*2 + 1로 구할 수 있으므로

 

점화식은 dp[i] = Math.min(dp[i], 1 + dp[i - (j*j)])가 된다.

 

my solution (Java)

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

public class _1699_ { // 제곱수의 합

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

		int n = Integer.parseInt(bf.readLine());

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

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

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

변수)
n : 주어진 자연수
dp : 제곱수 항의 최소 개수

 

자연수 n을 입력받는다. 1부터 n까지 살펴보며 초기값을 i로 설정한다. 그 이유는 최대 (1*1)로 i번 더하면 i값을 만들 수 있기 때문이다. 그다음 1부터 (j*j)가 i 이하일 때까지 살펴보며 dp[i]와 1+dp[i-(j*j)] 중 최솟값으로 업데이트한다. 

 

최종 dp[n]을 출력한다. 

---

---