hahn

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

코딩테스트 연습/백준(JAVA)

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

hahn 2021. 9. 14. 16:08
728x90
반응형

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

 

1010번: 다리 놓기

입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다.

www.acmicpc.net

http://boj.kr/612939ad94b94939a0464368b751d80e

 

공유 소스 보기

 

www.acmicpc.net

더보기
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으로 감당이 안 돼서

 

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

728x90
반응형