BOJ 1966 제곱수의 합

문제출처 : https://www.acmicpc.net/problem/1699

1. 문제요약

- 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있음

- 11 = 3^2 + 1^2 + 1^2(3개항)

  11 = 2^2 + 2^2 + 1^2 + 1^2 + 1^2(5개항)

- 11의 최소 제곱수 항의 갯수는 3개

- 자연수 N의 최소 제곱수 항의 갯수는?

- 1 <= N <= 100,000

2. 접근방법

- 임의의 정수 N에서

  1^2을 빼면 N-1

  2^2을 빼면 N-4

  ...

- d[n] 을 n의 최소 제곱수 갯수 라고 하면

  d[n] = min(d[0] + 1, d[1] + 1, d[2] + 1, d[3] + 1 ..., d[i <= j * j] + 1)

3. 시간복잡도

- 1 ~ 3 : 1 = 3

  4 ~ 8 : 2 = 2 * 5

  9 ~ 16 : 3 = 3 * 7

  17 ~ 25 : 4 = 4 * 9

  ...

- ∑(k = 1, 300)(2k + 1) * k = 2∑(k = 1, 300)k^2 + ∑(k = 1, 300)k

4. 회고

- 처음에 무조건 임의의 자연수 n에 가까운 제곱수를 구하면 되는 줄 알았는데

- 12 = 3^2 + 1^2 + 1^2 + 1^2 = 4개항

  12 = 2^2 + 2^2 + 2^2 = 3개항

※ 근데 맞은 소스랑 틀린 소스랑 차이가 없는데 왜 맞고 틀리지??????

채점 서버 문제였음..

소스코드 : 맞은 소스

#include <stdio.h>
#include <algorithm>
 
using namespace std;
 
int dp[100003];
 
int main() {
 
    int n;
    scanf("%d", &n);
    
    for (int i = 1; i <= n; i++) {
        dp[i] = 100000;
        for (int j = 1; j*j <= i; j++) {
            dp[i] = min(dp[i], dp[i - j*j] + 1);
        }
    }
 
    printf("%d\n", dp[n]);
 
}

소스 코드 : 틀린 소스 맞음

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

int n, d[100001];

int main(void){
	cin >> n;
	for (int i = 1; i <= n; i++){
		d[i] = 100000;
		for (int j = 1; j * j <= i; j++){
			d[i] = min(d[i], d[i - j * j] + 1);
		}
	}
	cout << d[n] << "\n";
	return 0;
}

[출처 : BOJ, 문제에 대한 모든 권리는 BOJ(acmicpc.net, startlink)에 있음]