글 읽기 - c++ 질문입니다

jh06038 2년 전 0

해당 문제를 풀 때 브루트 포스 알고리즘으로 주어진 수를 차례로 제곱근 처리한후 빼는 방식으로 한 다음, 최대 제곱근을 지속적으로 1씩 감소시키면서 최소 제곱근 수를 구하였습니다.

그런데 어떤 예시를 쳐도 맞는데, 채점에서는 틀리다고 합니다. 어디에서 틀렸는지 궁금합니다.

#include <iostream>
#include <cmath>
using namespace std;
int main() {
	int N, total = 0;
	cin >> N;
	int tmp = N;
	int min = 9999;
	int initc = sqrt(N);
	while (initc != 0) {
		int coef = initc;
		while (N != 0) {
			N -= coef * coef;
			coef = sqrt(N);
			total++;
		}
		if (min > total && total > 0)
			min = total;
		initc--;
		N = tmp;
		total = 0;	
	}
	cout << min;
}

dustkd1004 2년 전 0

반례 드릴게요

output : 4

answer : 3

이 문제는 dp로 풀어야 최적해를 구할 수 있어요

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

문제

문제

출처

ICPC

c++ 질문입니다

jh06038 2년 전 0

dustkd1004 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말