글 읽기 - 왜 틀렸습니다가 나올까요?

akdlzmf6979 2년 전 0

뭐가 잘못됐을까요?

당최 모르겠습니다..

논리적으로 잘못된 게 있을까요??

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

int n, cache[100001], sqr[1000];
//메모이제이션으로 해결
int least(int x)
{
	if(x == 0) return 0;
	int& ret = cache[x];
	if(ret != -1) return ret;
	ret = 1e9;
    //x 보다 작고 1 이상인 모든 제곱수에 대해 제곱수를 빼고 남은 수에 대해 최소한의 항의 수를 구하는 반복문 
	for(int i = 1; sqr[i] <= x; i++)
		ret = min(ret, least(x - sqr[i]));
	return ++ret;	
}

int main()
{
    //10만 이하의 제곱수 저장
	for(int i = 1; i * i <= 100000; i++)
		sqr[i] = i * i;
	cin>>n;
	memset(cache, -1, sizeof(int) * (n + 1)); 
	cout<<least(n);
}

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

문제

문제

출처

ICPC

왜 틀렸습니다가 나올까요?

akdlzmf6979 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말