[백준] 1699번 : 제곱수의 합

문제

 

---

풀이

 

myunji.tistory.com/319?category=1154147

[백준] 11052번 : 카드 구매하기

이 문제랑 결이 비슷한 것같다.

 

32를 제곱수의 합으로 나타낸다고 해보자.

일단 6^2 = 36으로 32보다 크기때문에 6을 쓸 순 없다.

 

그럼 5^2을 쓰면? 32-25니까 7이 남는다. 예제 입력 1을 보면 알겠지만 7을 표현하는 제곱수 항의 최소 개수는 4다.

그렇기 때문에 5^2를 사용하면 4+1 = 5가 될 것이다.

 

4^2를 써보도록 하겠다. 32-16이니까 16이 남는다. 16=4^2이기 때문에 32는 2개의 4^2로 나타낼 수 있다. 2가 나온다.

 

이런식으로 5^2부터 1^1까지 계산해본 뒤 항의 수가 가장 작은 것을 선택하면 된다. 32의 경우는 2가 될 것이다.

정리하자면 dp[n]이 n을 표현하는 제곱수 항의 최소 개수라고 할 때, dp[32]는

 

1+dp[7] (5^5+7)

1+dp[16] (4^4+16)

1+dp[23] (3^3+23)

1+dp[28] (2^2+28)

1+dp[31] (1^1+31)

 

중 최솟값이다.

---

소스코드

 

#include <iostream>
#include <cmath>
#include <algorithm>

using namespace std;

int dp[100001];

int dpSquared(int n) {
    for (int i = 1; i <= n; i++) {
        int squared = sqrt(i); //제곱근
        int result = 1 + dp[i - (squared * squared)]; //greedy(?)하게 구한 초기값. 만약 32라면 1+dp[7]
        for (int j = squared - 1; j >= 1; j--) //비교하며 최솟값 찾기. 1+dp[16], 1+dp[23]...
            result = min(result, 1 + dp[i - (j * j)]);
        dp[i] = result;
    }
    return dp[n];
}

int main() {
    int N;

    cin >> N;
    cout << dpSquared(N);
}

squared에 i의 제곱근을 integer로 저장하고, squared^2부터 1^1까지 비교해나가며 최솟값을 구한다.