글 읽기 - 중복순열로 풀었는데 시간 줄이는 방법

skesswswkk 3년 전 0

시간초과가 나는데 여기서 어떻게 더 시간을 줄일 수 있을까요?
조언 부탁드립니다.

#include <iostream>
#include <vector>
using namespace std;
//중복순열
int n, m;
int arr[30 + 5];

vector<int> v;
int ans_cnt;
void sol(int cnt) {
	if (cnt == n) {
		int sum = 0;
		for (int i = 0; i < n; ++i) {
			sum += v[i];
		}
		if (sum == m) {
			ans_cnt++;
		}
		return;
	}

	for (int i = 0; i < m; ++i) {
		v.push_back(arr[i]);

		sol(cnt +1);

		v.pop_back();
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;
	for (int i = 0; i < m; ++i) {
		arr[i] = i + 1;
	}

	sol(0);

	cout << ans_cnt << "\n";
}

herdson 3년 전 1

이항 계수 dp를 통해 중복 조합을 구하시면 됩니다.

skesswswkk 3년 전 0

@herdson

dp로 안 풀면 시간초과 나는 문제인건가요?

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

문제

문제

출처

ICPC

중복순열로 풀었는데 시간 줄이는 방법

skesswswkk 3년 전 0

herdson 3년 전 1

skesswswkk 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말