DP-1699(제곱수의 합)

1699번: 제곱수의 합 (acmicpc.net)

1699번: 제곱수의 합

 

본 문제는 제곱수의 합만으로 이루어진 숫자의 최소값을 구하는 문제입니다. 가장 적은 제곱수의 합으로 나타내기 위해서는 가장 숫자가 큰 제곱수로 본 숫자를 먼저 빼고 난 후 숫자를 제곱수의 합으로 구하는 것도 있지만, 자칫하면 반례가 있을수도 있기 때문에 아래에서 부터 제곱수의 합으로 이루어진 숫자의 최소값을 갱신하는 방식을 선택 하였습니다. 

 

 

package com.company;

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


public class Main {


    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        int dp[] = new int[t+1];

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

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