백준 1699번: 제곱수의 합

문제 링크 : https://www.acmicpc.net/problem/1699

15684번: 사다리 조작

 알고리즘 

 

문제는 어렵지않은 DP문제이다 .

동전 2문제처럼  작은수부터 차례로 채우고 높은수를 채울때 더 적은 갯수를 사용하는 경우를 저장 하는 방식으로 짜면 쉽게 풀린다 

 

 코드 

#include<iostream>
#include<algorithm>
 
using namespace std;
typedef long long ll;
 
ll n;
ll arr[100001];
 
int main() {
    cin.tie(NULL);
    ios::sync_with_stdio(false);
 
    for (int i = 1; i <= 10000; i++)arr[i] = 1000001;
 
    cin >> n;
 
    for (int i = 1; i <= n; i++) {
 
        for (ll j = i * i; j <= n; j++) {
            arr[j] = min(arr[j], arr[j - i * i] + 1);
        }
    }
 
    cout << arr[n];
 
}