● 2019.02.25 ~ 2019.03.31 단계별 풀어보기
: 2019.02.25 ~ 2019.03.31 기간동안 백준 단계별 풀어보기를 진행하고 그중 '이항계수 2' 를 정리한다.
이항 계수 2 성공
시간 제한메모리 제한제출정답맞은 사람정답 비율
1 초 | 256 MB | 13907 | 5228 | 4150 | 38.458% |
문제
자연수 N과 정수 K가 주어졌을 때 이항 계수 (NK)를 10,007로 나눈 나머지를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ K ≤ N)
출력
(NK)를 10,007로 나눈 나머지를 출력한다.
예제 입력 1 복사
5 2
예제 출력 1 복사
10
● 이항계수
참고 https://ko.wikipedia.org/wiki/%EC%9D%B4%ED%95%AD_%EA%B3%84%EC%88%98
이항 계수 - 위키백과, 우리 모두의 백과사전
위키백과, 우리 모두의 백과사전. 둘러보기로 가기 검색하러 가기 조합론에서, 이항 계수(二項係數, 영어: binomial coefficient)는 주어진 크기의 (순서 없는) 조합의 가짓수이다. 자연수 n {\displaystyle n} 및 정수 k {\displaystyle k} 가 주어졌을 때, 이항 계수 ( n k ) {\displaystyle \textstyle {\binom {n}{k}}} 는 다음과 같다. ( n k ) = { n ! / ( k
ko.wikipedia.org
※ 파스칼의 삼각형을 참고 하였을때
1
1 1
1 2 1 2는 두번째 줄의 1, 1 을 더해서 나온 결과
1 3 3 1 3은 세번째 줄의 1,2 // 2,1 을 더해서 나온 결과
위와 같은 조건을 보았을때 nCk = n-1Ck + n-1Ck-1 의 조건을 구할 수 있다.
※ 문제에서 주어는 N, K 의 범위를 고려했을때 단계별로 이항계수값을 구할때 마다 10007의 나머지를 구하는
방식으로 문제를 해결한다.
※ 중복되는 nCk 호출을 방지하여 불필요한 요소를 줄인다.
import java.util.Scanner;
public class Main {
static int[][] arr;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int K = sc.nextInt();
arr = new int[N+1][K+1];
loopM(N, K);
System.out.println(arr[N][K]);
}
public static int loopM(int n, int k) {
if(arr[n][k] >= 1) { // 이미 호출된적있는 경우 중복 계산 방지
return arr[n][k];
}else if(n == k || k == 0) { // 줄단위로 첫번째와 마지막은 1로 지정
return arr[n][k] = 1;
}else {
if(n-1 >= 0 && k-1 >= 0) { // 배열의 -값을 방지
arr[n][k] = loopM(n-1 , k-1) + loopM(n-1,k);
arr[n][k] %= 10007;
return arr[n][k];
}else {
return 0;
}
}
}
}
'백준 알고리즘' 카테고리의 다른 글
2019.02.11 ~ 2019.02.17 (0) | 2019.02.18 |
---|