[BOJ/C++] 17626: Four Squares

🥈 Silver 3

⭐️ 숫자 n 을 만드는데 필요한 제곱수 구하기(최대 4개)

✏️ 1차 솔루션

n 보다 작은 수 중에 가장 큰 제곱수는 무조건 포함한다고 생각했기 때문에 dp[n] = dp[n-(n보다 작은 수 중 가장 큰 제곱수)]+1 로 풀이

🚨 1차 trouble

솔루션 도출이 잘못 되었음.
이 방법으로 할 경우, 어떤 수에서는 제곱수의 개수가 4를 넘어가는 경우 발생

✏️ 최종 솔루션

⭐️ 숫자 n 보다 작은 제곱 수 중에 dp[n - 제곱 수] 가 가장 작은 값 + 1을 dp[n] 으로 설정

1. n 보다 작은 제곱수를 모두 vector 에 저장하면서 dp[제곱수]=1 로 세팅
2. 제곱수 vector 를 돌면서 dp[n - 제곱수] 가 가장 작은 값을 dp[n] 으로 지정

✏️ 최종 code

#include <iostream>
#include <vector>
using namespace std;

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

  vector<int> dp(n+1,0);
  vector<int> square;
  for(int i=1;i*i<=n;i++) {
      square.push_back(i*i);
      dp[i*i]=1;
  }

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

      int mx=5;
      for(int j=0;j<square.size();j++) {
          if(square[j]>i) break;

          mx=min(mx,dp[i-square[j]]);
      }

      dp[i]=mx+1;

  }

  cout << dp[n];

}