<Algorithm> 207. 이동하기(BOJ)

1. 11048번 이동하기(BOJ)

   사용 알고리즘 :  DP

• 2019/05/27 - [공부/Algorithm] - 206. 보행자천국(Programmers)  단순히 DP문제를 풀려고 했는데 신기하게 어제푼 문제랑 비슷했다. 

• 어제 푼 문제의 기초 버전 느낌이 든다... 무엇보다 경로느낌이 들면 DFS, BFS로 접근하려고 하는데 이제는 DP 먼저 생각을 해야겠다.

문제에 대한 접근&생각

1. (1,1) 부터 (n,m) 까지 최댓값 -> DFS, BFS? -> n과 m이 최대 1000 -> DP!
2. 대각선으로 내려오는 경우, 왼쪽에서 오는 경우, 위에서 내려오는 경우 중 최댓값-> DP(i,j) = Max[DP(i-1,j-1),DP(i-1,j),DP(i,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

import java.util.Scanner;   public class Main {     public static void main(String[] args) {         Scanner sc = new Scanner(System.in);         int n = sc.nextInt();         int m = sc.nextInt();         int[][] dp = new int[n+1][m+1];         /***************************          * DP를 활용하여 i,j로 들어올 수 있는          * 최대의 경우를 구한다. 즉          * 대각선으로 진입하는 경우, 왼쪽에서          * 오는 경우, 위에서 오는 경우 중          * 큰 값을 누적한다.           ***************************/         for(int i = 0; i < n; i++) {             for(int j = 0; j < m; j++) {                 dp[i+1][j+1] = sc.nextInt();             }         }         for(int i = 1; i <= n; i++) {             for(int j = 1; j <= m; j++) {                 dp[i][j] += Math.max(dp[i-1][j-1],Math.max(dp[i-1][j],dp[i][j-1]));             }         }         System.out.println(dp[n][m]);     } }   Colored by Color Scripter

cs