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

#문제

www.acmicpc.net/problem/1699

1699번: 제곱수의 합

#풀이 & 학습한 내용

dp[i]를 i의 제곱수 항의 최소개수로 정의하자. 그러면 소스코드의 12~17행에 해당하는 obtimal substructure를 얻을 수 있다. 이때 j를 sqrt(i)까지 반복한다는 것에 주목하자. 이를 위해 #include<cmath>를 추가해줬다.(j<=sqrt(i)를 j*j<=i로 변경가능하다) dp[i]에 맨 처음에는 최악의 경우인 모두 1로 구성될 경우의 'i'를 넣어주고, j를 1부터 sqrt(i)까지 증가시키며 dp[i-j*j]+1과 dp[i]를 비교해 최소의 개수를 필요할 경우 갱신시켜준다. 

 

#소스코드

#include<iostream>
#include<algorithm>
#include<cmath>
 
using namespace std;
 
int dp[100002];
 
int main(void) {
    int N;
    cin >> N;
    for (int i = 1; i <= N; i++) {
        dp[i] = i;//모두 1로만 구성된 최악의 경우
        for (int j = 1; j <= sqrt(i); j++) {
            dp[i] = min(dp[i], dp[i - j * j] + 1);
        }
    }
    
    cout << dp[N] << '\n';
}

github.com/HoYoungChun/BOJ_algorithm/blob/master/Dynamic_Programming/BOJ_1699.cpp

HoYoungChun/BOJ_algorithm