[BOJ - JAVA] 1010 - 다리 놓기(DP, 조합)

# 주소

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

1010번: 다리 놓기

 

# 문제

 

# 문제 해설 및 코드 리뷰

import java.util.*;
import java.io.*;
public class Main{
    public static int N;
    public static int M;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        long[] arr = new long[n];
        for(int i = 0; i < n; i++){
        	st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            M = Integer.parseInt(st.nextToken());
            System.out.println(Combination(N,M));
        }
    }
    public static long Combination(int N, int M){
        //MCN
        long son = 1;
        long mom = 1;
        
        if(N < M){
            for(int i = M; i > M-N; i--){
                son = son * i;
            }
            for(int i = N; i >= 1; i--){
                mom = mom * i;
            }
        }
        return son / mom;
    }
}

처음 작성한 코드입니다.

누가봐도 조합 문제이기에 조합을 구현해서 적용시켰는데 이상하게 예제에 있는거로는 풀어지는데 정답만 제출하면 틀립니다.

뭐가 틀렸는지 아직도 모르겠어요. 혹시 아시는 분 계시다면 말씀해주세요.

입력값의 경계값 분석에서도 다 작동하는데 정답만 제출하면 틀리네요 ㅎㅎ... 그래서 다른 사람의 코딩 풀이를 보고 참고해서 다시 코딩했습니다. 이 분은 long타입이라고 안하고 double타입으로 풀이했네요.. 이게 다른가???

import java.util.*;
import java.io.*;
public class Main{
    public static int N;
    public static int M;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        long[] arr = new long[n];
        for(int i = 0; i < n; i++){
        	st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            M = Integer.parseInt(st.nextToken());
            System.out.printf("%.0f\n", Combination(M,N));
        }
       }
    public static double Combination(int N, int M){
        //MCN
        double son = 1;
        double mom = 1;
        
        for(double i = N; i > N - M; i--)
        	son = son * i;
        for(double i = M; i > 0; i--)
        	mom = mom * i;
        return son / mom;
    }
}

딱 하나 다른게 있다면 long, int타입이 아닌 double타입으로 풀이했습니다. 이클립스에선 둘 다 똑같이 작동하는데 왜 틀린지 모르겠네요 ㅎㅎ..

어떤 분은 조합의 성질을 이용해서 nCr = n-1Cr-1 + n-1Cr 의 성질을 이용하여 푸셨던데, 우리 학원 학생들이 마침 고2의 이항 정리 파트를 끝낸 참이여서 이렇게도 풀 수 있다는데에 감명 받았습니다.

점화식 파트기 때문에 그 분의 방식으로 푸는게 더 적합할지 모르겠습니다. 

https://st-lab.tistory.com/194

[백준] 1010번 : 다리 놓기 - JAVA [자바]

여기에서 확인하시면 되겠습니다.

감사합니다.