[백준 11051번] 이항 계수 2 Java 풀이

이 글은 혼자 학습한 내용을 바탕으로 작성되었습니다.

틀리거나 잘못된 정보가 있을 수 있습니다.

댓글로 알려주시면 수정하도록 하겠습니다.

---

1. 문제

2. 입력

3. 출력

4. 예제

 

5. 풀이

이항 계수는 이항 계수의 수를 나열한 삼각형 모양의 파스칼 삼각형이 있습니다.

파스칼 삼각형

이 파스칼 삼각형을 이용하여 문제를 풀 수 있습니다.

 

먼저 파스칼 삼각형을 배열을 통해 쉽게 이용할 수 있게 그림을 변경해 보도록 하겠습니다.

1
1	1
1	2	1
1	3	3	1
1	4	6	4	1
1	5	10	10	5	1

세로 열 Index를 변수 N으로 가로 행 Index를 변수 K라고 한다면

 

유추가능한 점화식으로는 dp[N][K] = dp[N-1][K-1] + dp[N-1][K]라는 점화식이 도출된다.

 

단 N의 값이 0이면 dp[N][K]의 값은 1이 됩니다.

 

도출된 점화식과 예외 사항을 가지고 코드를 작성하면 아래와 같은 코드가 작성됩니다.

6. 코드

전체 코드는 Git에 있습니다.

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer strToken;
strToken = new StringTokenizer(br.readLine());

int n = Integer.parseInt(strToken.nextToken());
int k = Integer.parseInt(strToken.nextToken());

long[][] dp = new long[n+1][1001];

for(int i=0; i<=n; i++){
	for(int j=0; j<=i; j++){
		if(j == 0)
			dp[i][j] = 1;
		else
			dp[i][j] = (dp[i-1][j-1] + dp[i-1][j]) % 10007;
	}
}

bw.write(dp[n][k] % 10007 + "\n");
bw.flush();