글 읽기 - C++ 어디가 틀린 것인지 모르겠습니다.

jhkim990212 2년 전 0

C++ 어디가 틀린 것인지 모르겠습니다.

#include <iostream>
using namespace std;

long long D[100001];//memorization
int go(int N) {
	if (N == 1) return D[1] = 1;//초기값 설정
	if (D[N] != 0) return D[N];//memorization
	int ans = 100000;
	for (int i = 1; i*i <= N; ++i) {
		int tmp = go(N - i * i) + 1;
		if (tmp < ans) ans = tmp;
	}
	return D[N] = ans;
}

int main() {
	int N;
	cin >> N;
	cout << go(N) << '\n';
	return 0;
}

dladydwo123 2년 전 1

4을 넣으면 1이나와야하는데 4가 답으로 나옵니다.

그이유는 go 문에 0을 넣으면 0을 출력해야 하는데

int ans = 100000;
for (int i = 1; i*i <= N; ++i) {
int tmp = go(N - i * i) + 1;
if (tmp < ans) ans = tmp;
}
return D[N] = ans;

의 메커니즘 특성상 for문을 돌리지 않고 그대로 ans을 출력하기 때문입니다.

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

문제

문제

출처

ICPC

C++ 어디가 틀린 것인지 모르겠습니다.

jhkim990212 2년 전 0

dladydwo123 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말