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

https://www.acmicpc.net/problem/1699

1699번: 제곱수의 합

 

dp로 해결가능한 문제

 

에라토스테네스의 체에서 소수를 구하는 방법이 있다. 이를 이용하여 제곱수 또한 미리 저장해놓는 경우를 생각해보았다.

 

해보니까 안되서 경우의 수를 다 써보았다.

 

1 = 1

2 = 1 + 1

3 = 1 + 1 + 1

4 = 4

5 = 4 + 1

6 = 4 + 1 + 1

7 = 4 + 1 + 1 + 1

8 = 4 + 4

9 = 9

10 = 9 + 1 

 

쓰다보니 하노이 탑이 떠올랐다. 1씩 더하다가 제곱인 수를 만나면 그 전꺼를 더하는 식의 구성인 셈이다.

 

예를들면 dp[7] = dp[4] + dp[3] 과 같이 표현할 수 있고 

 

dp[10] = dp[9] + dp[1] 로 표현할 수 있다.

 

#include <iostream>
#include <algorithm>
using namespace std;
int dp[100001] = { 0, };
 
int main(int argc, char* argv[])
{
    int n;
    cin >> n;
    for (int i = 0; i <= n; i++) dp[i] = i;
 
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j * j <= i; j++) {
            dp[i] = min(dp[i], dp[i - j * j] + 1);
        }
    }
    cout << dp[n];
 
    return 0;
}

 

솔직히 잘 이해가 되지 않는 문제였다. 좀 더 실력을 키우고 다시 보자.