백준 6591번 이항 쇼다운

문제 링크입니다: https://www.acmicpc.net/problem/6591

순열과 조합을 배웠다면 풀 수 있는 문제였습니다.

알고리즘은 아래와 같습니다.

1. nCr = nCn-r 이기 때문에 연산 횟수를 줄이기 위해 K를 min(K, N-K)로 지정해줍니다.

2. nCr = nPr / r! 입니다.

->따라서, 1~K까지 반복문을 돌리면서 결과에서 나누어주고 N--를 곱해줍니다.

3. 결과는 int형이지만 중간 계산 과정에 long long형이 등장할 수 있기 때문에 주의해줘야합니다.

#include <iostream>

#include <algorithm>

#include <cstring> //memset

using namespace std;

 

int N, K;

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0); //cin 실행속도 향상

 

        while (1)

        {

                 cin >> N >> K;

                 if (N == 0 && K == 0)

                         break;

       

                 long long result = 1;

                 //nCr=nCn-r

                 K = min(K, N - K);

 

                 //nCr= nPr / r!

                 for (int i = 1; i <= K; i++)

                 {

                         result *= N;

                         result /= i;

                         N--;

                 }

                 cout << result << "\n";

        }

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~