백준 알고리즘, 1699 문제

---

풀이

# 무조건 큰 제곱수를 빼는것이 최소 횟수가 아니다.

67 = 64 + 1 + 1 + 1        --> 4개

67 = 36 + 25 + 4          --> 3개

즉, 67 보다 작은 제곱근들 (1, 4, 9, 16, 25, 36, 49, 64) 에 대하여

1.    67 - 1 로 시작하는 경우

2.    67 - 4 로 시작하는 경우

3.    67 - 9 로 시작하는 경우

...

8.    67 - 64 로 시작하는 경우

를 모두 알아보아야 한다.

"DP[N] = N 의 최소 제곱수의 합의 개수" 라고 한다면

DP 배열이 1 ~ N 까지 채워져 나가는 반복문 안에서                            ---> i

1 ~ (i*i) 의 제곱수를 빼나가며 최소값을 찾는 과정이 들어가야 한다.    ---> j

점화식은

    for (i = 1; i <= N; i++) {
        DP[i] = i;
        for (j = 2; j * j <= i; j++) {
            DP[i] = min(DP[i], DP[i - (j * j)] + 1);
        }
    }

이렇게 표현되는데 여기서 DP[i] 를 비교해주는 이유는

DP[3] = 1 + 1 + 1  ---> 3 개

의 경우처럼 1 로 만 구성된 개수를 고려하기 위함이다.

---

코드

@github 에서 보기

/**
 * @site: https://www.acmicpc.net/problem/1699
 * @github: https://github.com/7772
 * @auth: Landon Park
 * @date: 2018. 08. 09
 */
#include <iostream>
using namespace std;
int min(int a, int b) {
    return (a < b) ? (a) : (b);
}
int main() {
    int DP[100001];
    int i, j, N;
    cin >> N;
    for (i = 1; i <= N; i++) {
        DP[i] = i;
        for (j = 2; j * j <= i; j++) {
            DP[i] = min(DP[i], DP[i - (j * j)] + 1);
        }
    }
    cout << DP[N] << endl;
    return 0;
}

### 위 코드의 비교식 처럼 자기 자신을 비교하는 경우

불필요한 함수의 호출 없이 if 문으로 구성할 수 있다.

시간이 많이 줄어들 것이다.

/**
 * @site: https://www.acmicpc.net/problem/1699
 * @github: https://github.com/7772
 * @auth: Landon Park
 * @date: 2018. 08. 09
 */
#include <iostream>
using namespace std;
int main() {
    int DP[100001];
    int i, j, N;
    cin >> N;
    for (i = 1; i <= N; i++) {
        DP[i] = i;
        for (j = 2; j * j <= i; j++) {
            if (DP[i] > DP[i - (j * j)] + 1) {
                DP[i] = DP[i - (j * j)] + 1;
            }
        }
    }
    cout << DP[N] << endl;
    return 0;
}