acmicpc

[BAEKJOON] 1699. 제곱수의 합

코드와이 2021. 4. 27. 22:50

 

DP

문제링크

www.acmicpc.net/problem/1699

 

1699번: 제곱수의 합

어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다

www.acmicpc.net

 

package acmicpc.Silver3;

import java.util.Scanner;

public class 제곱_수 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		
		int[] arr = new int[n+1];
		arr[0] = 0;
		arr[1] = 1;
		
		for(int i = 2 ; i <= n ; i++) {
			arr[i] = 987654321;
			for(int j = 1 ; j*j <= i ; j++) {
				arr[i] = Math.min(arr[i], 1 + arr[i-j*j]);
			}
		}
		System.out.println(arr[n]);
	}
}