글 읽기 - 틀린점을 도저히 못찾겠어서 질문드립니다

rlaud1998 5년 전 0

10만보다 작은 제곱수까지 미리 다 구해서 모든 경우를 탐색할 수 있도록 짰는데 틀린점을 모르겠습니다...

도와주세용...

#include<iostream>
#include<algorithm>
using namespace std;
#define f(i,k,n) for(int i=k;i<n;i++)

int cache[100001];
int need[316];
int n;

int main()
{
	cin >> n;
	f(i, 1, 317)
	{
		need[i - 1] = i * i;
		cache[i*i] = 1;
		if (n == i * i)
		{
			cout << 1;
			return 0;
		}
	}
	f(i, 2, n + 1)
	{
		if (cache[i])continue;
		cache[i] = 1000;
		for (int j = 0; i - need[j] > 0; j++)
            cache[i] = min(cache[i], cache[i - need[j]] + 1);
	}
	cout << cache[n];
}

rlaud1998 5년 전 0

감사합니다 ㅠㅠ

메모리에 대한 생각은 전혀 하지못한것 같습니다...

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

틀린점을 도저히 못찾겠어서 질문드립니다

rlaud1998 5년 전 0

rlaud1998 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말