문제

풀이 방법

겹치면 안된다. 따라서 다음과 같이 풀었다.(예제 입력인 3-10, 1,2,5로 설명)

1.전부 1로 채우는 경우

2.전부 1로 채우는 경우에 무조건 '2'가 한개 이상 들어가는 경우

3.전부 1,2로 채우는 경우에 무조건 '3'이 한개 이상 들어가는 경우

3까지 가면 완료이다!

코드

#include <iostream>
using namespace std;
int main()
{
    unsigned int dp[10001] = {0,};
    int arr[100] = { 0, };
    int n, k,x=0,y=1,r=0;
    cin >> n >> k;
    for (int i = 0; i < n; i++) cin >> arr[i];
    dp[0] = 1;
    for (int i = 0; i < n; i++) {
        for (int j = arr[i]; j <=k; j++) {
            dp[j] += dp[j - arr[i]];
        }
    }
cout << dp[k]<<endl;
    return 0;
}

문제

해결방법

step1. 1,4,6,9같은 제곱수에 1을 넣어준다.

step2. 나머지 숫자들을 찾아준다.

for (a = 1; a <=sqrt(i); a++) {
#dp[i]를 구하고자한다.
#min( dp[i-1^2]+1, dp[i-2^2]+1, dp[i-3^2]+1....dp[i-sqrt(i)^2] ) 이다.
                if (dp[i - a * a] < minx)

                minx = dp[i - a * a];

            }

dp[i] = minx + 1;

코드

#include <iostream>
#include <math.h>
#include <algorithm>
using namespace std;
int main()
{
    int input;
    int dp[100010];
    cin >> input;
    dp[1] = 1;
    int a;
    int minx;
    int i, j;
    for (i = 1; i <= sqrt(input); i++) {
        dp[i*i] = 1;
    }
    for (i = 2; i <= input; i++) {
        if (dp[i] == 1)
            continue;
        else {
            minx = 100001;
            for (a = 1; a <=sqrt(i); a++) {
                if (dp[i - a * a] < minx)
                    minx = dp[i - a * a];
            }
            dp[i] = minx + 1;
        }
    }
    cout <<dp[input];
    return 0;
}