글 읽기 - 맞추기는 했는데 확실히 알고 싶어서 질문드립니다ㅠ

haggie 5년 전 0

아래는 제가 처음에 생각해낸 코드인데, 시간초과가 떠서 정답처리를 못 받았습니다. 아래 square함수를

int square(int* dp, int n) {

if (dp[n] > 0) {

return dp[n];

} else {

int min = n;

for (int i = 1; pow(i, 2) < n; i++){

if (min > square(dp,n - (int)pow(i, 2)) + 1) {

min = square(dp,n - (int)pow(i, 2)) + 1;

}

dp[n] = min;

return dp[n];

}

이렇게 바꾸니까 정답처리가 되었습니다. 차이점을 알고 싶습니다.. 이상하게도 비주얼스튜디오에서 인풋을 9999를 넣으면 둘다 안되는데 어떻게 위 코드는 정답처리가 되었는지 모르겠습니다. 이러면 사실은 틀린건가요?? 부탁드립니다!

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

int square(int* dp, int n) {
	if (dp[n] > 0) {
		return dp[n];
	}
	else {
//		cout << '1' << endl;
		int min = n;
		for (int i = 1; i < n / 2 + 1; i++) {
//			cout << '2' << endl;
			if (square(dp, i) + square(dp, n - i) < min) {
//				cout << '3' << endl;
				min = square(dp, i) + square(dp, n - i);
			}
		}
		dp[n] = min;
	}
	return dp[n];
}

int main() {
	int n;
	scanf("%d", &n);
	int* dp = new int[n + 1];
	for (int i = 0; i < n + 1; i++) {
		dp[i] = -1;
	}
	for (int i = 0; pow(i, 2) <= n; i++) {
		dp[(int)pow(i, 2)] = 1;
	}
	for (int i = 0; i < n + 1; i++) {
		square(dp, i);
	}
	printf("%d", square(dp, n));
	return 0;
}

adfsfsf 5년 전 0

위의 것으로 제출해보았는데 정답처리 됩니다. 뭔가 잘못 입력하신 것 같습니다. 그게 아니면 컴파일러에 문제가 있어서 제출시마다 결과가 달라지는 듯합니다. 그리고 팁을 드리자면, dp값을 i값이 낮은 값부터 채워넣으셨기 때문에 dp[n - (int)pow(i, 2)] 값이 항상 채워져 있으므로 굳이 재귀적으로 쓰실 것 없이 아래와 같이 쓰셔도 됩니다.

int square(int* dp, int n) {
	int min = n;
	for (int i = 1; pow(i, 2) < n; i++) {
		if (min > dp[n - (i * i)] + 1) {
			min = dp[n - (i * i)] + 1;
		}
	}
    if(dp[n]!=-1)
        dp[n] = dp[n]<min?dp[n]:min;
    else
        dp[n] = min; 
	return dp[n];
}

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

문제

문제

출처

ICPC

맞추기는 했는데 확실히 알고 싶어서 질문드립니다ㅠ

haggie 5년 전 0

adfsfsf 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말