반응형
14494번 다이나믹이 뭐예요?
https://www.acmicpc.net/problem/14494
14494번: 다이나믹이 뭐예요?
(1, 1)에서 (n, m)에 도달하는 경우의 수를 구하여라. 단, 경우의 수가 엄청 커질 수 있으므로 경우의 수를 1,000,000,007(=109+7)로 나눈 나머지를 출력한다.
www.acmicpc.net
Comment
DP문제의 기초격 문제
DP는 기초라고해도 왜이리 생각하기 어려운지 모르겠다..
hint
dp배열의 저장값 : 해당 지점에 도달하는 경우의 수
점화식 : 우측, 하단, 우하단 세가지 경우의 수를 활용
Solution
DP의 기초격 문제라 그런가 DP를 조금 맛본 상태에서 접했더니 점화식이 생각났던 얼마안되는 문제
먼저 dp배열을 만들고 해당 dp배열의 상단(우측으로만 진행하는 경우의 수) 하단(아래로만 진행하는 경우의 수)의 값은 도달하는 방법이 한가지 뿐이다. 때문에 먼저 초기화해서 쭉 1로 채워준 후에 해당 값을 가지고 남은 dp배열 모두를 채워나가면 되는데, 점화식은 위에 hint에 적었던 우측, 하단, 우하단 을 받는 이전dp배열을 가져오면 된다.
즉, dp[i][j] = dp[i - 1][j] + dp[i][j-1] + dp[i-1][j-1]; 로 해결이 된다
그림예시
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 | import java.io.*; import java.util.*; /** * dp 다차원배열 도달할 수 있는 경우의 수 */ public class Main { public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n, m; StringTokenizer st =new StringTokenizer(br.readLine()); n = Integer.parseInt(st.nextToken()); m = Integer.parseInt(st.nextToken()); int[][] dp = new int[1001][1001]; for(int i = 1; i <= n; i++){ dp[i][1] = 1; } for(int i = 1; i <= m; i++){ dp[1][i] = 1; } //값 초기화 끝 for(int i = 2; i <= n; i++){ for(int j = 2; j <= m; j++){ dp[i][j] = (((dp[i-1][j] + dp[i][j-1]) % 1000000007) + dp[i-1][j-1]) % 1000000007; } } System.out.println(dp[n][m]); } } | cs |
반응형
'공부 > Algorithm' 카테고리의 다른 글
| 백준 2310번 어드벤처 게임 자바로 풀어 본 짧은 글 (0) | 2023.11.28 |
|---|---|
| 백준 12755번 수면 장애 자바로 풀어 본 짧은 글 (0) | 2023.11.21 |
| 백준 1680번 쓰레기 수거 자바로 풀어 본 짧은 글 (0) | 2023.09.07 |
| 백준 1417번 국회의원 선거 자바로 풀어 본 짧은 글 (0) | 2023.08.17 |
| 백준 골드5 달성! (0) | 2023.08.11 |