C++/DP
DP-1699(제곱수의 합)
꿈을보는섬
2021. 1. 16. 10:29
1699번: 제곱수의 합
어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다
www.acmicpc.net

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