BOJ_11048_이동하기

1

구분: 다이나믹 프로그래밍

언어: Java

전략:

다이나믹 프로그램에서 memoization을 해당 칸에서 가질 수 있는 최대값으로 설정

• 문제에서 제시한 것은 원래 갈 수 있는 칸은 왼쪽 그림이다.
• 1칸 기준으로 보면 3 방향에서 올 수 있다. 이 3방향 중 가장 큰 부분과 내 값을 더해서 값을 갱신한다.
• col = 0인 부분은 왼쪽에서만 접근할 수 있고, row = 0인 부분은 위에서만 접근할 수 있다. --> 이 부분을 초기화 가능하며, 초기화 한다.

 

---

2 코드

import java.util.Scanner;
public class Main {

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int h = scanner.nextInt();
		int w = scanner.nextInt();
		int[][] map = new int[h][w]; //전체 숫자를 받을 배열
		int[][] d = new int[h][w]; //각 칸에 최대값을 삽입한다.- 각 칸은 3가지 칸에서 올 수 있다.
		for(int i = 0; i<h; i++) {
			for(int j = 0; j<w; j++) {
				
				map[i][j] = scanner.nextInt();
			}
		}
		//초기화 과정 - d[][0], d[0][]는 딱 아래 혹은 옆에서 올 수 있다  
		d[0][0] = map[0][0];
		for(int i = 1; i<w; i++) {
			d[0][i] = map[0][i]+d[0][i-1];
		}
		for(int i = 1; i<h; i++) {
			d[i][0] = map[i][0]+d[i-1][0];
		}
		
		//3방향에서 오는것 중 최대를 골라 d를 갱신한다.
		for(int i = 1; i<h; i++) {
			for(int j = 1; j<w; j++) {
				d[i][j] = Math.max((Math.max(d[i-1][j], d[i][j-1])), d[i-1][j-1])+map[i][j];
			}
		}

		System.out.println(d[h-1][w-1]);
	}

}

---

3

 

다이나믹 프로그래밍을 이요하여 문제를 푼다. 

점화식을 어떻게 세우는가가 가장 중요한것 같다.