https://www.acmicpc.net/problem/2225
2225번: 합분해
첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다.
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
34
35
|
import java.util.Scanner;
public class Main {
public static int n;
public static int k;
public static long[][] dp;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
k = sc.nextInt();
dp = new long[201][201];// k개를 이용해서 n을 만듦
for (int i = 0; i <= n; i++) {
dp[1][i] = 1; //1개를 이용해서 0~n만듦
}
for (int i = 1; i <= k; i++) {
dp[i][0] = 1; //1~k개를 이용해서 0을 만듦
}
for (int i = 2; i <= k; i++) {
for (int j = 1; j <= n; j++) {
for (int t = 0; t <= j; t++) {
dp[i][j] += dp[i - 1][j - t] % 1000000000;
}
dp[i][j] %= 1000000000;
}
}
System.out.println(dp[k][n] % 1000000000);
}
}
|
cs |
우선 나는 2차원 배열을 만들어줬다 예를 들어 dp[2][3]은 2가지 숫자를 통해 3을 만드는 것을 의미한다.
예를 들어 dp[3][3]을 구한다고 생각해보자.
(1,1,1) (1,0,2) (3,0,0) --> 1+6+3=10 같은 것이 있는 순열 생각하면된다.
그러면 이걸 dp 즉, 앞선 누적합을 통해 점화식으로 일반화하는 것을 생각해야한다.
예를 들어 내가 0을 선택하면 나머지 2가지 숫자로 3을 만드는 경우 dp[2][3]
1을 선택하면 나머지 2가지 수로 2를 만드는 경우 dp[2][2]
2를 선택하면 나머지 2가지수로 1을 만드는 경우 dp[2][1]
3을 선택해서 나머지 2가지 수로 0을 만드는 경우 dp[2][0]
두가지나 세가지를 선택하는 경우의 수는 생각할 필요 없다. 어차피 dp[2][i]에 다 누적되어 저장되어 있을 것이다.
점화식으로 나타내면
dp[i][j]=dp[i-1][j]+dp[i-1][j-1] ...... +dp[i-1][0] 이 된다.
이걸 반복문으로 나타내면
for (int i = 2; i <= k; i++) {
for (int j = 1; j <= n; j++) {
for (int t = 0; t <= j; t++) {
dp[i][j] += dp[i - 1][j - t] % 1000000000;
}
dp[i][j] %= 1000000000;
}
}
이렇게 삼중for문이 나타나는 것이다..!
또 다른 방법
표를 그리다가 우연히 규칙을 하나 더 발견했다. 아무래도 삼중 for문은 좀 에바다 싶기도 해서..허허
dp[2][3] = dp[2][2] + dp[1][3]인것을 알 수 있다
그러면 이중 for문을 통해서 점화식을 세울 수 있다.
for (int i = 2; i <= k; i++) {
for (int j = 1; j <= n; j++) {
dp[i][j] += (dp[i - 1][j] + dp[i][j - 1]) % 1000000000;
}
}
|
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
|
import java.util.Scanner;
public class Main {
public static int n;
public static int k;
public static long[][] dp;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
k = sc.nextInt();
dp = new long[201][201];// k개를 이용해서 n을 만듦
for (int i = 0; i <= n; i++) {
dp[1][i] = 1;
}
for (int i = 1; i <= k; i++) {
dp[i][0] = 1;
}
for (int i = 2; i <= k; i++) {
for (int j = 1; j <= n; j++) {
dp[i][j] += (dp[i - 1][j] + dp[i][j - 1]) % 1000000000;
}
}
System.out.println(dp[k][n] % 1000000000);
}
}
|
cs |
풀면서 잘못 생각한 부분/틀린부분
배열을 초기화 할때 문제가 있었다.
|
1
2
3
4
5
6
|
for (int i = 1; i <= n; i++) {
dp[i][0] = 1;
dp[1][i] = 1;
}
|
cs |
처음에는 위와 같이 코드를 썼는데
dp[i][0]에서 i는 n까지가 아닌 k까지만 반복문을 돌려주면 됐고 (예를 들어 20가지 방법을 이용해서 0을 만들 필요는 없기 때문) <-- 궁극적으로 틀린이유가 n까지 초기화해서 였다.
dp[1][i]는 1개를 이용해서 0을 만드는 방법의 수도 있기 때문이다.
참고한 사이트
https://fbtmdwhd33.tistory.com/80
[백준,BOJ 2225] 합분해( JAVA 구현)
-내 생각 처음 문제를 접했을 때는 어떻게 접근해야 할지 감이 잡히지 않았다. 그러나 조금 생각해 봤더니 어느 정도 길이 보였다. 처음 접근한 방법은 각 경우의 수를 따져보는 것이었는데, 이
fbtmdwhd33.tistory.com
<초기화 관련>
[백준 알고리즘] 백준 2225번 합분해 자바(Java)
츄르사려고 코딩하는 코집사입니다. 1. [백준 알고리즘] 백준 2225번 합분해 자바(Java) 1) 문제번호 : 2225번 2) 문제 출처 www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으..
yongku.tistory.com
'알고리즘 > DP' 카테고리의 다른 글
| [C++백준] 실버 1 / 1932번 정수 삼각형 (0) | 2022.02.28 |
|---|---|
| [C++ 백준]실버 5/1010번 다리놓기 (0) | 2022.02.12 |
| [java 백준] 골드 3/ 11054번 가장 긴 바이토닉 수열 (0) | 2021.08.15 |
| [java 백준] 실버 3/9461번 파도반 수열 (0) | 2021.08.10 |
| [java 백준] 실버 1/ 11052번 카드 구매하기 (0) | 2021.08.10 |
댓글