11051번 이항계수2

문제링크 : www.acmicpc.net/problem/11051

11051번: 이항 계수 2

 

 

<문제 풀이 근거>

   1) 파스칼 삼각형 이용

1

1 1

1 2 1

1 3 3 1

1 4 6 4 1 

=> pascal[i][j] = pascal[i-1][j-1]+pascal[i-1][j]

   2) 모듈러 연산 속성 이용

 ( a + b ) % M = ( ( a % M ) + ( b % M ) ) % M

 

 

 

<알고리즘>

  1) 주어진 N번째 열까지 파스칼 삼각형을 구한다.

  2) 이때 수가 int 범위를 초과하는 경우를 고려하여 모듈러 연산을 이용해 10007의 나머지로 계산한다.

  3) N행의 K번째 값을 출력한다.

 

 

 

방법1. Scanner 입력 이용 ( 메모리 : 16820KB    시간 : 128ms )

import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int K = sc.nextInt();
		
		int num[][] = new int[N+1][N+1];
		
		for(int i =0;i<N+1;i++) {
			for(int j =0;j<=i;j++) {
				if((j==0)||(j==i)){
					num[i][j]=1;
				}
				else {
					num[i][j] = (num[i-1][j]%10007+num[i-1][j-1]%10007)%10007;
				}
			}
		}
		System.out.println(num[N][K]%10007);
	}
}

 

 

방법2. BufferedReader을 이용한 입력 ( 메모리 : 15596KB   시간 : 96ms)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;

public class Main{
	public static void main(String[] args) {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		String s= "";
		try {
			s= bf.readLine();
		}catch(IOException e) {}
		StringTokenizer st = new StringTokenizer(s);
		int N = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
		
		int num[][] = new int[N+1][N+1];
		for(int i =0;i<N+1;i++) {
			for(int j =0;j<=i;j++) {
				if(j==0||j==i) {
					num[i][j] = 1;
				}
				else {
					num[i][j] = (num[i-1][j-1]%10007+num[i-1][j]%10007)%10007;
				}
			}
		}
		System.out.println(num[N][K]);
	}
}

 

 

+) 참고

  1) 파스칼 삼각형 : ko.wikipedia.org/wiki/%ED%8C%8C%EC%8A%A4%EC%B9%BC%EC%9D%98_%EC%82%BC%EA%B0%81%ED%98%95

파스칼의 삼각형 - 위키백과, 우리 모두의 백과사전

  2) 모듈러 연산 : www.crocus.co.kr/1231

모듈러 연산(Modular Arithmetic)