백준 1010번 다리(Java)

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

1010번: 다리 놓기

 

<문제점>

1. 분수의 경우, 분모 분자 따로 계산하기

우선 처음에, 분모 분자를 따로 계산하지 않고, 하나의 result라는 변수에서 조합을 계산하려고 한 점에 문제가 있었다.

분자에 해당하는 숫자를 차례로 곱하고(8*7*6..), 이후 분모에 해당하는 숫자를 차례로 나누는(../3/2/1) 방식이었다.

이 방식의 문제는 나머지에 있었다. 차례로 분모에 해당하는 숫자를 나누는 과정에서 약분이 되지 않는다면,

정수로 값이 떨어지지 않기 때문이다.

 

그래서 분모 분자를 각각 따로 계산한 후, 최종적으로 '분자/분모'의 형태를 취하기로 하였다.

 

2. 범위 문제

처음 int 자료형을 사용했는데, 큰 수로 바뀌니 마지막 예제값 출력에 오류가 났다.

그래서 1차로 long으로 바꿔주었는데, 이 또한 더 큰 값에 대해서는 범위 초과로 오류가 발생했다.

정수형의 최대 자료형인 long에서도 오류가 발생했기에,

실수형의 최대 자료형인 double로 바꾸어주고, 마지막 결과값 출력에서 double을 long으로 형변환해주었다.

 

이렇게 하니, 주어진 예제 뿐 아니라, 질문 게시판에 올라온 반례에 대해서도 모두 올바른 결과값이 나왔다.

그치만, 그럼에도 불구하고 결과는 계속해서 "틀렸습니다." 였다.

 

3. 그리고 또..?

질문 게시판을 통해 반례 또한 계속해서 찾아보고, 내가 직접 조합 계산기를 활용해 반례를 찾아보기도 하였으나

모든 값이 정확하게 나왔기에 문제가 무엇인지 찾는데에 꽤나 오랜 시간이 걸렸다.

그러던 중 다리 놓기 FAQ 라는 제목의, 다음과 같은 글을 발견하였다.

---

단순히 조합을 구하는 문제이지만, 구하는 방법에 따라 자주 틀리는 요인이 있습니다.

 

1. nCk를 n!/k!(n-k)!로 계산할 경우, 분자의 팩토리얼을 계산하면서 오버플로우가 날 수 있습니다. (파이썬은 정수 오버플로우가 없으므로 제외) 30팩토리얼은 무려 265252859812191058636308480000000, unsigned long long에도 담을 수 없을 정도로 큰 수입니다.

2. nCk를 n (n-1) ... (n-k+1) / k!로 계산할 경우 가능은 한데, 무턱대고 그냥 계산하면 마찬가지로 오버플로우가 납니다. nCk = nC(n-k)를 이용해 보세요.

3. 극도로 큰 수까지 나타낼 수 있는 double을 (파이썬은 float) 쓰면 되지 않느냐 하면 그것도 아닙니다. 부동소수점은 넓은 범위의 수를 나타내기 위해 어느 정도의 오차를 가지도록 설계되었기 때문에, 정수를 다루는 용도로는 절대 사용하면 안 됩니다. https://ko.wikipedia.org/wiki/...

계산 순서를 잘 바꿔서 큰 수가 나타나지 않도록 하면 int 오버플로우 없이도 정확한 값을 계산할 수 있습니다. 어떻게 하면 될까요?

---

 

위의 글에서 내가 주의 깊게 본 것은 바로 2번이었다. '어라 그냥 계산하면 되지 않나?' 싶었는데,

막상 조합계산기를 돌려보니 특정한 예제에서(모든 예에 해당하는 오류X)

정말 소수점 한 자리로 인한 일의 자리 범위의 작은 오차가 발생했다.

if ((m/2)<n) {
	n=m-n;
}

그래서 다음과 같은 조건문을 넣어 문제를 수정했다.

 

import java.util.Scanner;
public class B1010 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		double t, n, m;
		double num=1, den=1, k=1;
		t=sc.nextInt();
		for(int i=0; i<t; i++) {
			n=sc.nextInt();
			m=sc.nextInt();
			if ((m/2)<n) {
				n=m-n;
			}

			for(int j=0; j<n; j++) { // n번 반복
				num=num*m;
				m--;
			}

			for(int j=0; j<n; j++) { // n번 반복
				den=den*k;
				k++;
			}

			System.out.println((long)(num/den));
			num=1;
			den=1;
			k=1;	
		}	
	}
}

결과적으로, 몇 번의 시도 끝에 성공!