[백준 1699] 제곱수의 합

0. 제목

• 백준 1699 제곱수의 합
• BOJ 1699 제곱수의 합
• C++ 1699 제곱수의 합

---

1. 문제

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

---

2. 풀이

• dp방식을 사용하였다.
• 먼저 dp의 각 원소들을 1로만 이루어진 개수로 초기화시켰다.
• 이중반복문에서 i와 j는 1부터 시작할 필요가 없다. 이유는 dp[i] = i 여기서 초기화를 했는데 모두 1로 이루어진 경우를 나타낸 것이다. 따라서 2부터 시작해도 상관이 없다. 오히려 더 빠르다.
• dp[i] = min(dp[i], dp[i-j*j] + 1); 이 부분은 dp[i] 즉, 초기에 설정했던 값과 dp[i-j*j]+1 중 최솟값을 고르는 것이다.
• dp[i-j*j] 에 1을 더해주는 이유는 j*j에서 항이 1개 나오기 때문이다.
• 그리고 j가 2부터 i*i 보다 작거나 같은 동안 반복하기 때문에 최솟값이 계속 갱신될 수 있다.
• 반복문이 끝나고 나면 dp[1]부터 dp[N] 까지의 값이 모두 구해진다.

---

3. 코드

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