[SW expert Academy] SWEA 5607번 조합 자바(Java)

@notepad_jj2

츄르사려고 코딩하는 코집사입니다.

---

1. [SW expert Academy] SWEA 5607번 조합 자바(Java)

1) 난이도 : D3

 

2) 문제번호 : 5607번

 

3) 문제 출처

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXGKdbqczEDFAUo&categoryId=AWXGKdbqczEDFAUo&categoryType=CODE&problemTitle=%EC%A1%B0%ED%95%A9&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1

SW Expert Academy

 

2. 문제

자연수 N와 R가 주어진다. 이 때의 N combination R의 값을 1234567891로 나눈 나머지를  출력하세요.

예를들면 N이 4, R이 2라면 4 combination 2는 (4 * 3) / (2 * 1) = 6이 된다.

 

3. 제약사항

- 

4. 입력

첫 줄에 테스트케이스의 개수 T가 주어진다. (1 ≤ T ≤ 20)

각 케이스의 첫 줄에 정수 N, R이 주어진다. (1 ≤ N ≤ 1000000, 0 ≤ R ≤ N)

 

5. 출력

각 테스트케이스마다 한 줄에 걸쳐, 테스트케이스 수 “#(TC) “를 출력하고, N combination R을 1234567891로 나눈 나머지를 출력하시오.

 

6. 풀이

- 

7. 소스 코드

import java.io.*;
import java.util.*;

public class Main {
    static int N;
    static int R;
    
    static int MOD = 1234567891;
    
    static long factorial[];
    
    public static long pow(long a, long b) {
    	//지수가 0이면 1 리턴
        if(b==0) return 1;
        
        //지수가 1이면 밑 리턴
        else if(b==1) return a;
        
        //분할정복
        //b가 짝수면 temp를 2번 곱하면 된다.
        //예를 들어, 2^10을 분할정복하면 2^5 2^5로 나뉘기 떄문에 temp*temp
        if(b%2==0) {
            long temp = pow(a,b/2);
            return (temp*temp)%MOD;
        }
        
        //b가 짝수가 아니면 temp에 밑을 곱한다.
        // 2^9일 경우 2^4 2^4 2 를 곱해야 하기 때문에
        long temp = pow(a,b-1)%MOD;
        return (temp*a)%MOD;
    }
     
    public static void main(String[] args) throws Exception{
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt(); // 테스트 케이스 개수

        factorial = new long[1000001];
        
        factorial[0]=1;
        
        //팩토리얼 MOD로 나눠 저장하기
        for(int i=1;i<1000001;i++) factorial[i]=(factorial[i-1]*i)%MOD;
        
        for(int tc=1;tc<=T;tc++) {
            N = sc.nextInt();
            R = sc.nextInt();
            
            long a = factorial[N];
            long b = (factorial[N-R]*factorial[R])%MOD;
            
            b = pow(a,MOD-2);
            
            System.out.println("#"+tc+" "+(a*b)%MOD);
        }
    }
}

---