단계별로 풀어보기(정수론 및 조합론 - 다리 놓기)

1010번: 다리 놓기 (acmicpc.net)

1010번: 다리 놓기

http://boj.kr/612939ad94b94939a0464368b751d80e

공유 소스 보기

import java.util.Scanner;

class Main{
    
    public static void main(String[] args){
        
        Scanner sc = new Scanner(System.in);
        
        int testCaseCount = sc.nextInt(),
            leftCombination, rightCombination, divide;
        
        long result, store;
        
        for(int i = 0; i < testCaseCount; i++){
            
            rightCombination = sc.nextInt();
            leftCombination = sc.nextInt();
            
            divide = 1;
            result = 1;
            
            for(int j = leftCombination; j > leftCombination - rightCombination; j--){
            	
                result *= j;
                
                if(rightCombination >= divide) {
                	store = result % divide;
                	result /= divide;
                	result += store;
                	divide++;
                	
                }
                
            }
            
            while(rightCombination >= divide) {
            	store = result % divide;
            	result /= divide;
            	result += store;
            	divide++;
            }
            
            
            System.out.println(result);
            
        }
        
    }
    
}

조합 구하는 문제

 

수가 너무 커져서 long으로 감당이 안 돼서

 

나누고 몫 더해주는 거 반복함.