[java] 백준/1010 다리놓기

위의 문제는 다이나믹 프로그래밍으로 풀수 있는 문제 유형이다.

다리를 직접 그려서 해보는 것이 가장 빠르게 이해가 편하다.

n은 서쪽 사이트 m은 오른쪽 사이트로 볼때 

n = 1 일때는 dp[1][m] = m 이다

dp[2][4] = dp[1][1]+dp[1][2]+dp[1][3];

dp[n][m] = dp[n-1][1]+dp[n-1][2] ......dp[n-1][m-2]+dp[n-1][m-1];

package practice;   import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.StringTokenizer;   public class Bridge {       public static void main(String[] args) throws Exception{         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));         BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));         int n = new Integer(br.readLine());         for(int i=0;i<n;i++){             StringTokenizer st = new StringTokenizer(br.readLine());             int N = new Integer(st.nextToken());             int M = new Integer(st.nextToken());             long dp[][] = new long [N+1][M+1];             for(int a=0;a<=M;a++){                 dp[1][a] = a;             }             for(int a=1;a<=N;a++){                 //N                 for(int b=a;b<=M;b++){                 //B에다가                     for(int k=b;k>=a;k--){                         //반복해서 넣기                         dp[a][b]+=dp[a-1][k-1];                     }                 }                              }             bw.write(dp[N][M]+"\n");                      }         bw.close();     }   }