백준17213 - 과일서리

https://www.acmicpc.net/problem/17213

17213번: 과일 서리

수학적 요소를 중시하는 문제이다.

처음에는 브루트 포스를 사용하려 했지만 문제를 잘 읽어보니 중복조합을 사용하면 될 것 같았다.

N개의 요소 중 M개를 중복하여 선택하는 문제이다.

 

N개의 요소는 모두 적어도 1개를 뽑아야 하는 조건이 있다.

따라서 최종적으로 M은 M - N이 된다.

​

오랜만에 수학적 요소가 중요하다고 느끼는 문제이다.

#include <iostream>
using namespace std;


int main() {
	int a, b; //a는 입력받을 과일의 갯수, b는 훔칠 과일의 갯수
	long long int bunja = 1, bunmo = 1; //분자와 분모를 나타낸 변수, 콤비네이션을 사용하기 위해 자료형으로 long long int를 선언
    
	cin >> a;
	cin >> b;
    
	b = b - a; //최소 a개의 과일을 적어도 1번은 사용하기 때문에 선언
    
	if (b == 0) { //콤비네이션의 r값이 0이면
		cout << 1; //콤비네이션 정의에 따라 1이 나와야 함
		return 0;
	}
    else { //1이 아니면
        a = a + b - 1; //중복조합에서 n + r - 1을 설정
	    if (a - b < b) { //연산 횟수를 줄이기 위해 사용, n - r < r이면
		    b = a - b; //r을 갱신
	    }
	    for (int i = a; i > a - b; i--) { //a부터 a - b + 1까지
		    bunja = bunja * i; //곱한다.
	    }
	    for (int i = b; i > 0; i--) { //b부터 1까지
		    bunmo = bunmo * i; //곱한다.
	    }
	    cout << bunja / bunmo;
    }
}