글 읽기 - 힌트 주실 수 있으실까요?

park780172 5년 전 0

문제 읽고

백트래킹으로 생각하여

다 구현하고 10 입력하니 244가 나오길래

제출하였더니 시간 초과가 뜨네요.

(시간 초과 예상은 했었으나, 마음만은 아니길 빌었습니다.)

여하튼 중복조합 공식(nHr)과는 답도 다르니,

생각을 계속 해봐도 잘 안 풀리네요.

혹시 힌트라도 주실 수 있으실까요??

#include <iostream>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
#include <map>
#include <set>

#pragma warning(disable:4996)  
#pragma comment(linker, "/STACK:336777216")

using namespace std;

int N = 0;

vector<int> v;

bool s[50*21] = { false, };

int cnt = 0;

void simulation(int sum, int pos)
{
	if (pos == N)
	{
		if (!s[sum])
		{
			s[sum] = true;
			++cnt;
		}

		return;
	}

	for (int i = 0; i < v.size(); i++)
	{
		sum += v.at(i);

		simulation(sum, pos + 1);

		sum -= v.at(i);
	}
}

int main(void)
{
	v.push_back(1);
	v.push_back(5);
	v.push_back(10);
	v.push_back(50);

	scanf("%d", &N);

	simulation(0, 0);

	printf("%d\n", cnt);

	return 0;
}

seico75 5년 전 0

지금하신 방법은 n자리에 4개의 숫자를 넣어본다로 접근하신 것 같습니다. 그러면 4^n 이니 1,099,511,627,776 정도 반복인데,

IXI 나 IIX 나 XII 나 같으니 이것을 생각한다면...

I 가 i1=0~n 번, V 는 i5 = 0~n - i1번, X는 i10 = 0 - i1 - i5 번, L 은 i50 = 0 - i1 - i5 - i10 번 나오는 경우로 생각해볼 수 있을 것 같습니다.

그러면 연산이 (n+1)^4 보다 작아지는 상황이니 194,481 보다 훨씬 작아질 것 같습니다.

결국 4번씩 n 번 재귀하는 것이 아니라 n(보다 작은 숫자)만큼 4번 재귀하는 방법으로 접근하는 것이 좋을 것 같습니다.

park780172 5년 전 0

답변 감사합니다!!!

해결에 도움이 됐습니다.

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

문제

문제

출처

ICPC

힌트 주실 수 있으실까요?

park780172 5년 전 0

seico75 5년 전 0

park780172 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말