반응형
🔺 문제
🔺 코드
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
34
35
36
37
38
|
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
// DP 배열 초기화
long[][] bridge = new long[31][31];
for(int i = 0 ; i <= 30 ; i++) {
bridge[i][0] = 1;
bridge[i][1] = i;
bridge[i][i] = 1;
}
// DP 수행
for(int i = 2 ; i <= 30 ; i++) {
for(int j = 1 ; j < i ; j++) { // 고르는 수가 전체 개수 넘지 않게
bridge[i][j] = bridge[i - 1][j] + bridge[i - 1][j - 1]; // 파스칼의 삼각형
}
}
StringBuilder sb = new StringBuilder();
int T = Integer.parseInt(br.readLine());
while(T --> 0) {
st = new StringTokenizer(br.readLine()," ");
int N = Integer.parseInt(st.nextToken()); // 서
int M = Integer.parseInt(st.nextToken()); // 동
sb.append(bridge[M][N] + "\n");
}
System.out.println(sb);
br.close();
}
}
|
cs |
✅ 해결 아이디어
✔ 조합!
- DP (점화식) : Bottom-UP 방식
💥 유의사항
• 20! 만 되어도 long 범위를 넘어간다고 함!
🔺 다른 풀이들
- 재귀로도 푼 방법! (메모이제이션)
💬 느낀 점
20!만 넘어도 long 범위를 넘어간다는 것을 기억해두자!
1회독 | 2회독 | 3회독 | 4회독 | 5회독 |
V | 230703 | 240628 |
(+ 230703 2회독)
위랑 별 차이 없음
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
34
|
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
StringBuilder sb = new StringBuilder();
int[][] dp = new int[31][31];
for(int i = 0 ; i < 31 ; i++) {
dp[i][0] = 1;
dp[i][i] = 1;
dp[i][1] = i;
}
for(int i = 1 ; i < 31 ; i++) {
for(int j = 2 ; j < 31 ; j++) {
dp[i][j] = dp[i-1][j] + dp[i-1][j-1];
}
}
int T = Integer.parseInt(br.readLine());
while(T --> 0) {
st = new StringTokenizer(br.readLine(), " ");
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
sb.append(dp[M][N]).append("\n");
}
System.out.println(sb);
}
}
|
cs |
(참고)
반응형
'코테 > 백준' 카테고리의 다른 글
[백준/JAVA] 1722번: 순열의 순서 (0) | 2023.05.11 |
---|---|
[백준/JAVA] 13251번: 조약돌 꺼내기 (0) | 2023.05.10 |
[백준/JAVA] 11051번: 이항 계수 2 (0) | 2023.05.10 |
[백준/JAVA] 11438번: LCA 2 (0) | 2023.05.10 |
[백준/JAVA] 11437번: LCA (0) | 2023.05.10 |