글 읽기 - 이 문제 어떻게 접근하는거죠?

yeongjae8066 4년 전 0

브루트포스로 접근해서 0.5초 안에 해결했는데 다른 분들 보니 쉽게 빠르게 푸시는 것 같은데 혹시

이 문제 원리가 어떤건가요?

#include <iostream>

using namespace std;

int n, m;
int ans;

void go(int kind, int cnt) {
	if (cnt == m - n) {
		ans += 1;
		return;
	}
	if (kind == n || cnt > m - n) {
		return;
	}

	for (int i = 0; i <= m - n; i++) {
		go(kind + 1, cnt + i);
	}

	return;
}

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	cin >> n >> m;
	for (int i = 0; i <= m - n; i++) {
		go(1, i);
	}

	cout << ans << '\n';
	return 0;
}

fldj2855 4년 전 1

중복조합 개념을 사용하여 더 빠르게 풀어낸게 아닐까 조심히.. 추측해봅니다

서로 다른 n개에서 r개를 고르는 경우 중복조합을 사용합니다 (n H r ==> c+r-1 C r )

fldj2855 4년 전 2

아 지금보니 오타가 있네요

(c+r-1 C r) 이 아니라 (n+r-1 C r)입니다..!

yeongjae8066 4년 전 0

감사합니다!!!!!!

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

문제

문제

출처

ICPC

이 문제 어떻게 접근하는거죠?

yeongjae8066 4년 전 0

fldj2855 4년 전 1

fldj2855 4년 전 2

yeongjae8066 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말