백준 프로그래밍 9343

선영이는 매우 긴 직선의 원점에 서 있다. 선영이는 왼쪽이나 오른쪽으로 한 번에 한 칸씩 이동할 수 있다.

2N번 움직여서 시작한 위치로 돌아오는 랜덤 걷기 문제의 경로의 수는 $\left(\begin{matrix} 2N \\ N \end{matrix}\right)$ 이다. 

시작한 점으로 다시 이동해야 하기 때문에, 왼쪽으로 이동한 횟수와 오른쪽으로 이동한 횟수가 같아야 한다. 따라서, N번 오른쪽으로, N번 왼쪽으로 움직이면 되기 때문이다.

선영이는 위의 문제에서 음수 좌표로 이동할 수 있다. 음수 좌표로 이동할 수 없는 조건을 추가했을 때, 경로의 수를 구하는 프로그램을 작성하시오. 예를 들어, N = 1인 경우에 선영이는 $0 \to 1 \to 0$ 으로 이동할 수 있다. 하지만, $0 \to -1 \to 0$으로는 이동할 수 없다.

문제 출처:https://www.acmicpc.net/problem/9343

결국 이항계수를 구하는 문제이다. 

랜덤워크를 그대로 해석하여 경우의 수를 찾기에는 실행시간이 부족할 것 같았다.

입력이 최대 1000개 들어오고, 각 입력에 대해 N의 최댓값이 1,000,000이었기 때문에.

위의 조건에 해당하는 경우의 수는 $\frac{1}{N+1} \left( \begin{matrix} 2N \\ N \end{matrix} \right)$ 이므로 해당 수를 바로 계산하여 출력하는 것을 목표로 했다.

문제에서 요구하는 것은 최대 1000개의 입력 N에 대해 random walk의 수를 1,000,000,007로 나눈 나머지를 출력하는 것. 참고로 해당 숫자는 소수.

전에 풀었던 문제인 이항계수$\left( \begin{matrix} N \\ k \end{matrix} \right)$를 구하는 코드를 가져와서 루프를 1000번 돌렸더니 시간이 넘어갔다.

매 입력에 대해 계산을 다시 하는 것이 힘든 것 같았다.

처음에는 modulo inverse를 구하는 더 빠른 알고리즘을 찾으려 했지만 Extended Euclidean Algorithm(EEA)보다 유의하게 빠른 알고리즘을 찾기는 힘들 것 같았다.

그래서 factorial계산을 매 번 처음부터 하지 말고, 작은 숫자를 먼저 처리하고, 그것을 이어받아 다음 큰 숫자를 처리하는 방식으로 하기로 했다.

여기서 문제는 그렇게 하기 위해서는 정렬이 필요한데, 출력은 원래 순서로 되돌려 출력해야 한다는 것.

입력을 저장해 놓고, 출력할 때 하나씩 비교해서 재정렬하기엔 역시나 시간이 오래 걸릴 것 같아서 tuple을 만들어서

첫 번째 Component는 입력받은 값을, 두 번째  component는 순서의 index를 저장하고, hashCode와 Comparable의 compareTo를 overriding해서 java.util.Array.sort()를 각 component를 기준으로 정렬하도록 했다.

입력받은 후에는 입력값을 크기순으로 sort해서 순차적으로 값을 구하고

그 이후에 두 번째 component를 이용해 원래 순서로 되돌리는 방식.

계산은 long type을 사용했지만, remainder의 크기가 1,000,000,007정도였기 때문에, 숫자를 세 번 이상 곱하면 long을 벗어날 가능성이 있어 숫자를 곱할 때 마다 remainder연산을 해 주어야 했다.

BigInteger를 써서 remainder연산을 매번 하지 않는 것 보다는 조금 귀찮더라도 primitive type을 쓰는 게 나은 듯.

아래는 코드

import java.util.Scanner;
import java.util.Arrays;
public class Main {	
	class FirstSort implements Comparable<FirstSort>{
		int[] entry=new int[2];
		public FirstSort() {}
		public FirstSort(int[] a) {
			entry[0]=a[0];
			entry[1]=a[1];
		}
		public int hashCode() {
			return entry[0];
		}
		public int compareTo(FirstSort y) {
			return this.hashCode()-y.hashCode();
		}
	}
	class SecondSort implements Comparable<SecondSort>{
		int[] entry=new int[2];
		public SecondSort() {}
		public SecondSort(int[] a) {
			entry[0]=a[0];
			entry[1]=a[1];
		}
		public SecondSort(FirstSort a) {
			entry[0]=a.entry[0];
			entry[1]=a.entry[1];
		}
		public int hashCode() {
			return entry[1];
		}
		public int compareTo(SecondSort y) {
			return this.hashCode()-y.hashCode();
		}
	}
	
	public long[] getInverseModP(long a, long b) { //return (A,B) such that aA+bB=1 AND the input should a>=b, relatively prime
		long[] rtn=new long[2];
		long[] temp=new long[2];
		if(b==1) {
			rtn[0]=0;
			rtn[1]=1;
		}
		else {
			temp=getInverseModP(b,a%b);
			rtn[0]=temp[1];
			rtn[1]=temp[0]-(a/b)*temp[1]; 
		}
		return rtn;
	}

	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		Main main=new Main();
		long divider=1000000007;
		
		int T=sc.nextInt();
		
		FirstSort[] inputs=new FirstSort[T+1];
		
		int[] constructor=new int[2];
		inputs[0]=main.new FirstSort(constructor);
		for(int i=1;i<=T;i++) {
			constructor[0]=sc.nextInt();
			constructor[1]=i;
			inputs[i]=main.new FirstSort(constructor);
		}
		Arrays.sort(inputs);

		
		long enumerator=1;
		long denominator=1;
		long denomTemp=1;
		
		for(int i=0;i<T;i++) {
			for(int j=inputs[i].entry[0];j<inputs[i+1].entry[0];j++) {
				enumerator=(enumerator*(2*j+1)%divider)*(2*j+2)%divider;
				denominator=(denominator*(j+1))%divider;
			}
			denomTemp=(((denominator*denominator)%divider)*(inputs[i+1].entry[0]+1))%divider;
			denomTemp=main.getInverseModP(divider,denomTemp)[1]%divider;
			if(denomTemp<0)
				denomTemp+=divider;
			inputs[i].entry[0]=(int)(enumerator*denomTemp%divider);
			inputs[i].entry[1]=inputs[i+1].entry[1];
		}
		

		SecondSort[] results=new SecondSort[T];
		
		for(int i=0;i<T;i++) {
			results[i]=main.new SecondSort(inputs[i]);
		}
		
		Arrays.sort(results);
		
		for(int i=0;i<T;i++) {
			System.out.println(results[i].entry[0]);
		}
	}
}