BOJ 17626 : Four Squares [C++]

문제

 

DP문제인걸 알아차리는데 한 5분 좀 더 걸린거 같다.

 

과정

1. 배열의 인덱스가 제곱수인 곳은 1로 채움
2. dp[i - 1] + 1이 dp[i]보다 작다면 dp[i]를 dp[i - 1] + 1로 갱신.
3. 1부터 루트n까지 순회하며 i + j * j가 n + 1보다 작고, 해당 인덱스(i + j * j) 값이 dp[i] + 1보다 크다면 dp[i] + 1로 갱신

 

#include <iostream>
#include <math.h>

int dp[50001];

void sol(int n){
    dp[1] = 1;
    dp[2] = 2;
    dp[3] = 3;
    for(int i = 1; i < n + 1; i++){
        if(i < (int)std::sqrt(n) + 1){
            if(i * i < n + 1){
                dp[i * i] = 1;
            }
        }
        if(dp[i - 1] + 1 < dp[i]){
            dp[i] = dp[i - 1] + 1;
        }
        for(int j = 1; j < (int)std::sqrt(n) + 1; j++){
            if(i + (j * j) < n + 1){
                if(dp[i] + 1 < dp[i + (j * j)]){
                    dp[i + (j * j)] = dp[i] + 1;
                }
            }
        }
    }
}

int main() {
    int n = 0;
    std::cin >> n;

    for(int i = 1; i < n + 1; i++){
        dp[i] = 9999;
    }

    sol(n);

    std::cout << dp[n] << "\n";
    return 0;
}

 

이렇게 해서 통과는 했는데, 다른 사람들 코드를 보니 더 효율적이었다.

내가 더 섬세하게 생각하지 않고, 이렇게 하면 되겠거니 하고 코드를 쓴 것 같다.

 

 

과정

1. dp[i] = dp[i - 1] + 1
2. dp[i - (j * j)] + 1 이 dp[i] 보다 작다면 dp[i]를 갱신

#include <iostream>
#include <math.h>

int dp[50001];

void sol(int n){
    dp[1] = 1;

    for(int i = 1; i < n + 1; i++){
        dp[i] = dp[i - 1] + 1;

        for(int j = 2; j < (int)std::sqrt(i) + 1; j++){
            if(dp[i - (j * j)] + 1 < dp[i]){
                dp[i] = dp[i - (j * j)] + 1;
            }
        }
    }
}

int main() {
    int n = 0;
    std::cin >> n;

    sol(n);

    std::cout << dp[n] << "\n";
    return 0;
}