글 읽기 - 제곱수의합 동전다이나믹으로 해결하려고 하는데 예외케이스좀 봐주세요 ㅜㅜ

nakgee 5년 전 0

배열 범위초과랑 버그 오류 다잡았는데

마지막에 틀렸습니다가 나오네요 ㅜㅜ 혹시 예외케이스가 있나요???

#include <iostream>
#include <stdio.h>
using namespace std;

int dy[100001];
int min(int a, int b) {
	if (a < b) return a;
	return b;
}
int main() {
	int n;
	cin >> n;
	int cnt = 1;
	while (cnt*cnt < n) {
		if (cnt*cnt > 100000) break;
		dy[cnt*cnt] = 1;
		cnt++;
	}
	cnt--;
	dy[1] = 1;
	for (int i = 2; i <= n; i++) {
		if (dy[i] == 1)continue;
		dy[i] = 999999999;
		for (int j = 1; j <= cnt; j++) {
			if (i - (j*j) <= 0) break;
			dy[i] = min(dy[i], dy[i - (j*j)] + 1);
		}
	}
	cout << dy[n];
    
	return 0;
}

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

문제

문제

출처

ICPC

제곱수의합 동전다이나믹으로 해결하려고 하는데 예외케이스좀 봐주세요 ㅜㅜ

nakgee 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말