Algorithm, boj, 쉬운 계단 수(10844)

풀이

• (r, c)에 있으면, (r+1, c), (r, c+1), (r+1, c+1)로 이동할 수 있다는 점에 주목한다
• 방한칸을 옮길때마다 (dp[i][j]) 해당 방의 위, 왼쪽옆, 왼쪽대각선위의 방 중에 가장 큰값과 해당 방의 값을 더해 최적의 값을 구한다.

package org.baekjoon;

import java.util.Scanner;

public class test11048_moving {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		int arr[][] = new int[n+1][m+1];
		int dp[][] = new int[n+1][m+1];

		int[] nx = {1, 0, 1};
		int[] ny = {0, 1, 1};

		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				arr[i][j] = 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] , Math.max(dp[i][j-1], dp[i-1][j-1])) + arr[i][j];		
			}
		}
		System.out.println(dp[n][m]);
	}

}

---

Reference

• 문제보러가기

---