https://www.acmicpc.net/problem/12785
12785번: 토쟁이의 등굣길
인하대학교에 다니는 토쟁이는 y축과 평행한 w개의 도로, x축과 평행한 h개의 도로가 있는 도시에 살고 있다. 토쟁이의 집은 이 도시의 맨 왼쪽 아래에 위치하며 좌표로는 (1, 1)로 표시할 수 있다.
www.acmicpc.net
- 처음엔 간단하게 생각해서 BFS로 구현을 했었는데, 풀고나니 메모리 초과가 발생해서 다시 dp로 풀었다.
📌 - 풀이
- 이 문제는 결국 출발점 -> 토스트 집의 경로 * 토스집의 경로 -> 도착점까지를 구하는 문제인데
- DP를 이용해서 해당하는 경로까지의 경우의 수를 업데이트 해주고 경로의 수를 곱해주면 결과값이 나온다.
🔥 - java code
package DP.S1_12785_토쟁이의등굣길;
import jdk.dynalink.NamespaceOperation;
import java.io.*;
import java.util.*;
public class Main {
public static int N,M,x,y;
public static int[] dx,dy;
public static long[][] dp;
public static void main(String[] args) throws IOException {
//BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedReader br = new BufferedReader(new FileReader("src/input.txt"));
StringTokenizer st = new StringTokenizer(br.readLine());
StringBuilder sb = new StringBuilder();
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
x = Integer.parseInt(st.nextToken());
y = Integer.parseInt(st.nextToken());
dp = new long[M][N];
for (int i=0;i<M;i++){
dp[i][0] =1;
}
for (int i=1;i<N;i++){
dp[0][i] = 1;
}
for(int i =1;i<M;i++){
for(int j=1;j<N;j++){
dp[i][j] = (dp[i-1][j] + dp[i][j-1])%1000007;
}
}
for(int i=0;i<M;i++){
System.out.println();
for(int j =0;j<N;j++){
System.out.print(dp[i][j] + " ");
}
}
System.out.println(dp[y-1][x-1]*dp[M-y][N-x] % 1000007);
}
}