조합, DFS, Memoization
Memoization https://soheeparklee.github.io/posts/DS-memoization/
✅ 조합의 경우수를 재귀를 이용해 계산하세요.
1
2
3
4
5
6
7
8
9
//input
5 3
//output
10
//input
33 19
//output
818809200
🟢 Code without memoization
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
class Main {
static int n;
static int r;
static int[][] memo;
public int DFS(int n, int r) {
if(n==r) return memo[n][r]= 1;
if(n==1 || r==1) return memo[n][r]= n;
else return memo[n][r]= DFS(n-1, r-1) + DFS(n-1, r);
}
public static void main(String[] args) {
Main T = new Main();
Scanner sc = new Scanner(System.in);
n= sc.nextInt();
r= sc.nextInt();
memo= new int[n+1][r+1];
System.out.println(T.DFS(n, r));
}
}
🟢 Code with memoization
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
class Main {
static int n;
static int r;
static int[][] memo;
public int DFS(int n, int r) {
if(n==r) return memo[n][r]= 1;
if(n==1|| r==1) return memo[n][r]= n;
else{
if(memo[n][r] == 0){
memo[n][r]= DFS(n-1, r-1) + DFS(n-1, r);
return memo[n][r];
}
else{
return memo[n][r];
}
}
}
public static void main(String[] args) {
Main T = new Main();
Scanner sc = new Scanner(System.in);
n= sc.nextInt();
r= sc.nextInt();
memo= new int[n+1][r+1];
System.out.println(T.DFS(n, r));
}
}
🟢 Cleaner Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Main {
static int[][] memo;
public int DFS(int n, int r) {
if(n==r || r==0) return memo[n][r]= 1;
if(memo[n][r] != 0) return memo[n][r];
else return memo[n][r]= DFS(n-1, r-1) + DFS(n-1, r);
}
public static void main(String[] args) {
Main T = new Main();
Scanner sc = new Scanner(System.in);
int n= sc.nextInt();
int r= sc.nextInt();
memo= new int[n+1][r+1];
System.out.println(T.DFS(n, r));
}
}
This post is licensed under CC BY 4.0 by the author.