[BOJ - JAVA] 11048 - 이동하기(DP)

[BOJ - JAVA] 11048 - 이동하기(DP)

728x90

반응형

# 주소

https://www.acmicpc.net/problem/11048

# 문제

# 문제 해설 및 코드 리뷰

import java.util.*; public class Main{ public static int n, m; public static int[][]arr; public static void main(String[] args) { Scanner scan = new Scanner(System.in); n = scan.nextInt(); m = scan.nextInt(); arr = new int[n+1][m+1]; for(int i = 1; i <= n; i++) { for(int j = 1; j <= m; j++) { arr[i][j] = scan.nextInt(); } } for(int i = 1; i <= n; i++) { for(int j = 1; j <= m; j++) { arr[i][j] += Math.max(arr[i-1][j], Math.max(arr[i][j-1],arr[i-1][j-1])); } } System.out.println(arr[n][m]); } }

DP의 가장 기본적인 문제라고 생각합니다.

그냥 오른쪽, 왼쪽, 대각선으로 이동할 때 마다 가장 큰 값을 비교하면 된다 생각했지만 그 이상의 행과 열에서 더 큰 값이 나올 수 있으므로 다른 방법으로 풀어야 합니다.

그래서 배열의 왼쪽과 위에 0으로 패딩을 합니다.(0으로 테두리를 만든다는 맥락)

그리고 나서 arr[i][j]의 값은 같은 행 왼쪽 열과 위쪽 행 같은 열, 왼쪽 행 왼쪽 열 중에서 가장 큰 값을 arr[i][j]에 더합니다. 그렇게 되면 차근 차근 모든 행과 열에 대해 더해진 값이 배열을 채우는 새로운 배열이 완성됩니다.

이 때는 DP를 이용하여 덧셈을 진행해주셔도 되고 그대로 arr를 사용하셔도 됩니다.

표를 이용하여 다시 설명드리자면

0 0 0 0 0 1 2 4 0 2 3 5

라는 배열이 있다고 생각해봅시다. 제일 왼쪽과 위에는 0으로 패딩한 결과입니다. 이 때 arr[2][4]가 가장 최대가 되려면

0 0 0 0 0 1 1 + 2 = 3 3 + 4 = 7 0 1 + 2 = 3 3 + 3 = 6 7 + 5 = 12

가 되어 결론적으로 12가 최대가 됩니다.

즉 모든 배열을 왼쪽, 위쪽, 왼위쪽의 값들을 각각 더한 것 중 최대값을 출력한다고 보면 되겠습니다.

처음엔 백트래킹으로 풀려고 하다가 시간 초과도 나고 넘 코드가 복잡해져서 DP문제답게 DP개념으로 풀었습니다.

728x90

반응형

from http://codingrapper.tistory.com/66 by ccl(A) rewrite - 2021-10-30 04:02:11