[1010] 다리 놓기 in Java

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

1010번: 다리 놓기

---

 

접근 방식

nCr을 사용하여 계산을 바로 해주는 방법을 사용함

nCr은 조합 개수를 구하는 공식

(n! / (n-r)! ) / r!

 

 

 

 

시행 착오

- 처음엔 중복 없는 조합을 떠올렸음

그래서 조합을 구하는 재귀를 돌려서 했으나 시간초과

 

- findAnswer이라는 함수와 변수 answer의 타입을 모두 int로 설정해주었을 때

아래 예시를 돌리면 정답이 아닌 0이 나오는 오류가 발생함

예시) 1 / 13 29

알고 보니 오버플로우 문제였음

오버플로우가 발생했을 때

1이 나오면 음수, 0이 나오면 양수값이라는 의미이다.

 

 

따라서 int를 double로 변경해줬음

 

 

 

 

 

 

 

 

 

package day_0810;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class n1010 {
    static double answer; 
    static int n;  // 서쪽에 있는 사이트의 개수
    static int m; // 동쪽에 있는 사이트의 개수
    
    public static double findAnswer(int n, int m) {
        double up=1;
        double down=1;
        for (int i = m; i >m-n; i--) {
            up*=i;
        }
        for (int i = n; i >0; i--) {
            down*=i;
        }
        return up/down;
        
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        StringTokenizer st;
        for (int t = 0; t < T; t++) {            
            st = new StringTokenizer(br.readLine());
            answer=0;
            n=Integer.parseInt(st.nextToken()); 
            m=Integer.parseInt(st.nextToken()); 
            answer = findAnswer(n, m); // mCn , m>=n
            System.out.printf("%.0f\n",answer);
        }
    }
}