백준 1699 제곱수의 합

문제

문제링크 : https://www.acmicpc.net/problem/1699

풀이전략

1. 시간은 2초로 충분하므로 O(n^2)으로 문제를 해결 할 수 있다.
2. 밑에서부터 순차적으로 구할 수 있다.

코드

#include<bits/stdc++.h>

using namespace std;

int N;
int dp[100001];

int main(){
    ios_base::sync_with_stdio(false);
    freopen("../input.txt","rt",stdin);
    
    cin >> N;
    dp[0] = 0;
    for(int i=1; i<=N; i++){
     
        dp[i] = i;
        // 핵심코드, 결국 i까지의 값을 찾으면 1^2부터 천천히 계산하여 그중 최소값을 찾으면 된다. 
        // 여기서 dp[i-j*j] +1 에서 1을 더해주는것을 잊으면 안된다. 결국 제곱수의 개수를 구하는 문제이기 때문이다. 
        for(int j=1; j*j <=i; j++){
            dp[i] = min(dp[i], dp[i - j*j]+1);
        }
    }
    cout << dp[N] << endl;
    return 0;
}

소감

나는 처음에 규칙을 찾으려고하여 결국 문제를 못풀었지만, 결국 시간복잡도를 계산해보면 O(n^2)으로도 충분한 문제였다. 항상 문제를 분석하고, input output을 비교해보고, base case를 생각하는 과정을 잊지말아야겠다.