[백준 11048번] 이동하기 Java 풀이

이 글은 혼자 학습한 내용을 바탕으로 작성되었습니다.

틀리거나 잘못된 정보가 있을 수 있습니다.

댓글로 알려주시면 수정하도록 하겠습니다.

---

1. 문제

2. 입력

3. 출력

4. 예제

5. 풀이

이번 문제는 DP를 이용하여 풀어 보았습니다.

 

준규는 오른쪽과 아래쪽 그리고 오른쪽 아래 대각선으로만 움직일 수 있습니다.

 

준규가 (2, 3)으로 이동한다면 이전 위치는 (2, 2), (1, 2), (1, 3) 3가지 위치에서 (2, 3)으로 이동이 가능합니다.

 

DP[2][1]의 값은 (1, 2)에서 가지고 있을 수 있는 사탕의 최대 개수이며 DP[2][2]의 값은 (2, 2)에서 가지고 있을 수 있는 사탕의 최대 개수이며 DP[3][1]의 값은 (1, 3)에서 가지고 있을 수 있는 사탕의 최대 개수가 됩니다.

 

그렇다면 준규가 (2, 3) 위치로 이동할 때 가져올 수 있는 최대의 사탕 개수는 (2, 2), (1, 2), (1, 3) 3 위치에서 가지고 있던 사탕의 개수 중 가장 큰 값의 사탕 개수에 (2, 3)에 있는 사탕을 더 한 개수가 (2, 3) 위치에서 최대의 사탕 개수가 될 것입니다.

 

위 과정으로 알 수 있는 것은 (X, Y)위치에서의 사탕의 최대 값은 Max( DP[Y][X-1], DP[Y-1][X], DP[Y-1][X-1] ) +

입력[Y][X]의 사탕 수가 된다는 것을 알 수 있습니다.

 

단 (1, 1)의 경우 시작 위치이므로 점화식을 통한 값이 아닌 입력으로 주어진 값을 입력 해야 됩니다.

 

DP의 구성은 최상단과 가장 좌측의 계산을 점화식을 통해 구성하기 위해 DP배열 행과 열에 1칸을 추가하고 0으로 모두 설정 하였습니다.

6. 코드

전체 코드는 Git에 있습니다.

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer stringTokenizer;

stringTokenizer = new StringTokenizer(br.readLine());

int row = Integer.parseInt(stringTokenizer.nextToken());
int col = Integer.parseInt(stringTokenizer.nextToken());

int[][] dp = new int[row + 1][col + 1];

for (int i = 1; i <= row; i++) {
	stringTokenizer = new StringTokenizer(br.readLine());

	for (int j = 1; j <= col; j++) {
		if (i == 1 && j == 1)
			dp[i][j] = Integer.parseInt(stringTokenizer.nextToken());
		else
			dp[i][j] = Math.max(dp[i - 1][j - 1], Math.max(dp[i - 1][j], dp[i][j - 1])) + Integer.parseInt(stringTokenizer.nextToken());
	}
}

bw.write(dp[row][col] + "\n");
bw.flush();