#1699 제곱수의 합

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

1699번: 제곱수의 합

실버 3의 문제였다. 디피는 항상 등록된(?) 티어보다 어려운것 같다.

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

long long dp[100001];

int main()
{
  //freopen("input.txt","r",stdin);
  int n;
  cin>>n;
  int num;

  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;
    }
  }

  cout<<dp[n];
}

풀이 과정은 다음과 같다.

dp[i] = i를 제곱수의 합으로 나타내었을때, 필요한 항의 최소 개수 라고 한다.

이때 마지막항에 오는 수가 중요하고, 마지막 항이 1일때, 4일때, 9일때 .... 로 계산한다.

마지막 항이 1일때: dp[i]=dp[i-1] + 1

마지막 항이 4일때: dp[i]=dp[i-4] + 1

마지막 항이 9일때: dp[i]=dp[i-9] + 1

....

이 중 최소 개수를 구해야 하므로, dp[i]=min(dp[i-j^2] + 1) 으로 쓸 수 있다.

 

이 문제도 마지막항을 잘 쳐다보면 그렇게 어렵지 않게 해결 할 수 있는 문제였다.