글 읽기 - 이문제는 dp를 쓰면 안되는건가요?..

andy15701 2년 전 0

고수분들 도와주세요!! 애초에 이렇게 풀면 안되는건가요?..

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <stdio.h>
#include <string>
#include <stack>
#include <math.h>
using namespace std;

int a;
int numcount = 0;

void dp(int a, int num, int lev, int lastnum) {
	if (lev > 5) {
		return;
	}
	else if (lev <= 4 && num == a) {
		numcount++;
		return;
	}
	else if (lev < 4) {
		if (lastnum == 0) {
			lastnum = 1;
		}
		for (int i = lastnum; i <= (int)sqrt(a); i++) {
			dp(a, num + i * i, lev + 1, i);
		}
	}
}

int main(void) {
	while (1) {
		scanf("%d", &a);
		if (a == 0) {
			return 0;
		}
		else {
			numcount = 0;
			dp(a, 0, 0, 0);
			printf("%d\n", numcount);
		}
	}
}

herdson 2년 전 0

dp 써도 되는 문제 맞습니다~

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

문제

문제

출처

ICPC

이문제는 dp를 쓰면 안되는건가요?..

andy15701 2년 전 0

herdson 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말