백준 1699 / 제곱수의 합

문제

풀이

설명

1,2,3 더하기와 유사한 문제이다.
어떠한 수들의 제곱을 더하면 N이 되는 문제이다.

이 문제는 N을 만들기 위한 제곱이들어가는 항의 최소값을 구하는건데

D[i] = i를 제곱수의 합으로 나타냈을 때, 필요한 항의 최소개수
라고 하면 최소개수 이전의 값은 D[n-i^2]이라고 할 수 있다.

즉 D[n] = min(D[N-i^2])+1 라고 할 수 있다.

코드

import java.util.Scanner;

public class Num1699 {

	public static void main(String[] args) {
		
		  Scanner sc = new Scanner(System.in);
		  
	        int n = sc.nextInt();
	        int[] d = new int[n+1];
	        
	        for (int i=1; i<=n; i++) {
	            d[i] = i;
	            for (int j=1; j*j <= i; j++) {
	                if (d[i] > d[i-j*j] + 1) {
	                    d[i] = d[i-j*j] + 1;
	                }
	            }
	        }
	        System.out.println(d[n]);
	}

}

코드설명

참고 :
출처 : https://www.acmicpc.net/problem/1912