글 읽기 - 이 방법은 안되는건가요? (시간초과)

tjdahr25 3년 전 0

배열을 사용하지 않고 재귀를 이용해봤는데

이 방법은 틀린건가요?

#include <iostream>
using namespace std;
long counts=0;

void simul(int n,int k, int num) {
	if (k > n) return;
	if(k==n) counts = (counts + 1) % 1000000000;
	if (num == 0) simul(n, k + 1, 1);
	if (num == 9) simul(n, k + 1, 8);
	else {
		simul(n, k + 1, num - 1);
		simul(n, k + 1, num +1);
	}
}

int main() {
	int n;
	cin >> n;
	for (int i = 1;i <= 9;i++) {
		simul(n, 1, i);
	}
	cout << counts;
	return 0;
}

djm03178 3년 전 0

시뮬레이션을 돌려서는 풀 수 없습니다. 경우의 수가 너무나도 많기 때문입니다.

재귀냐 배열이냐의 문제가 아니라, 시뮬레이션을 사용하지 않고 다이나믹 프로그래밍을 통해 효율적으로 해결해야 합니다.

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

문제

문제

출처

ICPC

이 방법은 안되는건가요? (시간초과)

tjdahr25 3년 전 0

djm03178 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말