(17) [C++, Java] 백준 No.1699 : 제곱수의 합

문제

풀이

자세한 풀이 : https://ldgeao99.tistory.com/entry/챕터3-18-DP-문제-풀이4-1-백준-No1699-제곱수의-합

 

# C++

#include<iostream>

using namespace std;

int d[100001];

int main()
{
    int n;
    cin >> n;

    for (int i = 1; i <= n; i++){
        d[i] = i; // 최대값을 초기값으로 넣어줌. 1을 i번 하면 최대값이기 때문. 
        for(int j = 1; j*j <= i; j++){
            if(d[i] > d[i -(j*j)] + 1)
                d[i] = d[i -(j*j)] + 1;
        }
    }

    cout << d[n] << "\n";
}

# Java

import java.util.*;

public class Main {
    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]);
    }
}