백준 1699 c++ "제곱수의 합" -PlusUltraCode-

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

 

[필자 사고]

동적 프로그래밍을 이용해 푼 문제이다.

필자는 처음에 제곱수를 어떻게 표현할지 고믾이였다.

2중 for문 방식을 이용하였고

첫번째 for문은 dp값을 갱신할 목적 

두번째 for문은 k*k로 제곱수를 통해 dp값을 갱신할 목적으로 사용했다.

처음 필자는 두번째 for문에서 k의 초기값을 1로설정 안하고 i로 설정해서 한참 애를 먹었다.

아래는 코드 상세한 해설이다.

[코드 해설]

•  

---

2. 시간 복잡도 분석

이중 반복문을 사용하므로 최악의 경우 시간 복잡도는 **O(N√N)**이 된다.

• 바깥 반복문: i가 1부터 N까지 반복 → O(N)
• 안쪽 반복문: k^2이 i 이하일 때까지 반복 → O(√N)

따라서 최악의 경우에도 효율적인 방법으로 문제를 해결할 수 있다.

[소스 코드]

#include <iostream>
#include <vector>
#include <algorithm> 

using namespace std;

int N;
vector<int> dp;

void Game_Start() {
    cin >> N;
    dp.resize(N + 1, N);

    dp[0] = 0;

    for (int i = 1; i <= N; i++) {
        for (int k = 1; k * k <= i; k++) {
            dp[i] = min(dp[i], dp[i - k * k] + 1);
        }
    }
    cout << dp[N];
}

int main() {
    Game_Start();
    return 0;
}