BOJ 11051 이항 계수2 [Java]
문제
접근방법
- 처음에 재귀나 반복으로 풀었을 때는 시간초과가 난다.
- 그래서 아래 그림과 같이 이항계수를 다시 이해하고, 동적 계획법으로 풀이하였다.
(출처 : https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=vollollov&logNo=220947452823)
구현
import java.io.*;
import java.util.*;
class Main {
public static void main(String[] args) throws Exception {
// for coding
// System.setIn(new FileInputStream("./input/input_11051.txt"));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine(), " ", false);
int N = Integer.parseInt(st.nextToken());
int K = Integer.parseInt(st.nextToken());
int[][] dp = new int[N + 1][N + 1];
for (int i = 0; i < dp.length; i++) {
for (int j = 0; j <= i; j++) {
if (i == j || 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] + "");
bw.close();
}
}
제출
Author And Source
이 문제에 관하여(BOJ 11051 이항 계수2 [Java]), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@sheltonwon/BOJ-11051-이항-계수2-Java저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)