[백준/JAVA] 11051번: 이항 계수 2
🔺 문제
11051번: 이항 계수 2
첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 1,000, 0 ≤ \(K\) ≤ \(N\))
www.acmicpc.net
🔺 코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
|
import java.util.*;
import java.io.*;
public class Main {
static int[][] D;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine()," ");
int N = Integer.parseInt(st.nextToken());
int K = Integer.parseInt(st.nextToken());
// DP 배열 초기화
D = new int[N + 1][N + 1];
for(int i = 1 ; i <= N ; i++) {
D[i][1] = i;
D[i][0] = 1;
D[i][i] = 1;
}
// DP 배열 채우기 (여기서 MOD 연산 수행)
for(int i = 2 ; i <= N ; i++) {
for(int j = 1 ; j < i ; j++) {
D[i][j] = D[i-1][j] + D[i-1][j-1];
D[i][j] %= 10007; // 모듈러 연산!
}
}
System.out.println(D[N][K]);
br.close();
}
}
|
cs |
✅ 해결 아이디어
✔ 조합
→ DP
→ 점화식
→ 모듈러 연산! (26번째 줄)
💥 유의사항
• 이전 문제보다 N 범위가 커졌고, 결과값을 10007로 나눈 나머지를 출력해야 함
⇨ 모듈러 연산
(A mod N + B mod N)mod N = (A+B)mod
🔺 다른 풀이들
- 모듈러 연산 설명까지.. 최고
[백준] 11051번 : 이항 계수 2 - JAVA [자바]
www.acmicpc.net/problem/11051 11051번: 이항 계수 2 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 1,000, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net 문제 이전의 이항 계수 1 문제와 같은 문제다. 다만 출력할 때 이항
st-lab.tistory.com
- 이렇게 푸신 분들이 더 많았다.
[백준] 11051번 : 이항 계수 2(JAVA)
https://www.acmicpc.net/problem/11051 11051번: 이항 계수 2 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 1,000, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net 위의 문제는 BaekJoon Online Judge의 단계별로 풀어보기 중 16단계
eungulife.tistory.com
💬 느낀 점
모듈러 연산을 잊지 말자!!
사실 조합 점화식도 잊은지 좀 되었다...하하하
앞에서 그래프 트리 풀다가
이런 수학.. 문제 (?) 푸니까 또 다르게 재밌는 것 같다
| 1회독 | 2회독 | 3회독 | 4회독 | 5회독 |
| V | 7/3 |
(참고)
✔ Do it 알고리즘 코딩테스트 자바편