[백준 / BOJ] acmicpc 1699 제곱수의 합 C++

문제

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

1699번: 제곱수의 합

 

dp[idx] = n ->  idx까지의 최대 연속합이 n이라는 의미이다.

dp[제곱수]는 무조건 1이다. 

따라서 처음엔 어떤 수던간에

dp[i] = dp[직전 제곱수] + dp[i-직전 제곱수]

즉 dp[i] = 1 + dp[i-직전 제곱수]

라는 공식을 세우고 풀었는데 틀렸다.

코드는 다음과 같았다. 

#include <iostream>
#include <string>
#include <string.h>
#include<algorithm>
#include <queue>
#include <vector>
#include <map>
#include <stack>
#include <string>
#include <cstring>
#include <set>
#include <sstream>
#include <deque>
#include <cmath>
using namespace std;
#define MAX 100001

int sqArr[317], dp[MAX]; //문제에서 최대값인 100,000의 루트 = 316.xx
int n;

int solve(){
    for(int i = 1; i<= n; i++){
        for(int j = 1; j<= 316; j++){
            if(i > sqArr[j])   continue;
            if(i == sqArr[j]){
                dp[i] = 1;
                break;
            }
            // i>j
            dp[i] = 1 + dp[i- sqArr[j-1]];
            break;
        }
    }
    return dp[n];
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin>>n;
    
    for(int i = 1; i <= 316; i++){
        sqArr[i] = i*i;
    }
    
    cout<< solve() <<"\n";

}

이런식으로.. 짰었다.

 

일단 가장 큰 문제점은 '1 + dp[i - 직전 제곱수]'보다도

더 전의 제곱수에서 최소 dp값이 나올 수 있다는 것이었다.

 

반례로 32 가 있었다.

내가 세운 공식대로라면

dp[32] = dp[25] + dp[32-25]

dp[32] = 1 + dp[7] = 5

로 5가 나오는 반면, 답은 다음과 같았다.

 

32 = 4^2 + 4^2 

-> dp[32] = 2

 

DP 초반 문제들에서 항상 조심해야 했던 점인데 이걸 생각하지 못했다.

 

그리고 이 외에도 제곱수를 저장하기 위해 sqrArr라는 배열을 만들고 초기화 해줬는데, 

이것도 쓸데없는 짓이었다.

 

 

아무튼 bottom-up으로 제대로 다시 푼 코드는 다음과 같다.

#include <iostream>
#include <string>
#include <string.h>
#include<algorithm>
#include <queue>
#include <vector>
#include <map>
#include <stack>
#include <string>
#include <cstring>
#include <set>
#include <sstream>
#include <deque>
#include <cmath>
using namespace std;
#define MAX 100001

int dp[MAX];
int n;

int solve(){
    for(int i = 1; i<= n; i++){
        dp[i] = i;
        for(int j = 1; j*j<= i; j++){
            if(dp[i] > dp[i-j*j]+1)
                dp[i] = dp[i-j*j]+1;
        }
    }
    return dp[n];
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin>>n;
    
    
    cout<< solve() <<"\n";

}

sqrArr는 전혀 쓸 필요 없이 2중 for문 안에서 조건문에 j*j<=i 라고 넣어주면 되는 것이었다..

 

1부터 j^2이 i 값를 넘어가지 않는 모든 j를 다 돌며

dp를 채워나가야 했었던 문제였다.