[백준] 11048번 이동하기

문제

준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다.

준규는 현재 (1, 1)에 있고, (N, M)으로 이동하려고 한다. 준규가 (r, c)에 있으면, (r+1, c), (r, c+1), (r+1, c+1)로 이동할 수 있고, 각 방을 방문할 때마다 방에 놓여져있는 사탕을 모두 가져갈 수 있다. 또, 미로 밖으로 나갈 수는 없다.

준규가 (N, M)으로 이동할 때, 가져올 수 있는 사탕 개수의 최댓값을 구하시오.

입력

첫째 줄에 미로의 크기 N, M이 주어진다. (1 ≤ N, M ≤ 1,000)

둘째 줄부터 N개 줄에는 총 M개의 숫자가 주어지며, r번째 줄의 c번째 수는 (r, c)에 놓여져 있는 사탕의 개수이다. 사탕의 개수는 0보다 크거나 같고, 100보다 작거나 같다.

출력

첫째 줄에 준규가 (N, M)으로 이동할 때, 가져올 수 있는 사탕 개수를 출력한다.

 

이 문제는 절대로 완탐으로 풀면 안된다.

왜냐하면 시간 초과가 발생하기 때문이다.ㅎㅎ

 

그럼 어떻게 해야할까?

바로 다이나믹 프로그래밍 즉, 동적 계획법으로 풀어야 한다.

나는 이용어가 익숙하지 않으므로..ㅜㅜ 내 나름대로 이유를 들어 설명하면

중복되는 코드를 제거하는 알고리즘? 방법?이라고 생각한다. (모든 dp가 이렇지는 않지만... 내 수준에서는 이렇다.)

 

이 문제 같은 경우에도

이걸 완탐으로 푼다고 생각하자.

그러면 dfs로 풀게될것 이고...

dx = {} dy = {} 를 지정해서 풀게 될게 뻔하다.

그러면 이동하면서 그 값이 그전과 값과 큰지 아닌지 확인해야한다.

만약 크다면 그 값으로 바꾸고 아니라면 바꾸면 안된다.

이 짓을 배열끝까지 갈때까지 반복해야 한다.

근데 문제는 같던곳을 또 반복하게 된다.

이 짓을 최소화 할 수 있는 방법이 있을까?

 

그래서

 

#include <bits/stdc++.h>
using namespace std;

int n,m;  

int arr[1010][1010];

int main(void) {    
  ios_base::sync_with_stdio(false); 
  cin.tie(NULL);

  cin >> n >> m;

  int temp; 
  arr[0][0] = 0;
  for(int i = 1;i <=n;i++) {
    for(int j = 1;j<=m;j++) {  
       
       cin >> temp;
       int mx = -1;
       mx  = max(mx,
             max(arr[i-1][j-1],
             max(arr[i-1][j],arr[i][j-1]))); 
       
       arr[i][j] = temp + mx; 
    }
  }


  cout << arr[n][m];


  
}

 

코드를 이렇게 만들었다.

arr[0][0] 는 딱히 이유없지만,.. 그냥 넣었다.ㅎㅎ 

1부터 시작하는 이유는 만약 0부터 시작하면 -1도 포함되어지기 때문이다.

 

저런 식이 가능한 이유는

문제에서

준규가 (r, c)에 있으면, (r+1, c), (r, c+1), (r+1, c+1)로 이동할 수 있고, 각 방을 방문할 때마다 방에 놓여져있는 사탕을 모두 가져갈 수 있다.

라는 것으로 봤을때.

준규가  (2,2)에 있다면 3,2 / 2,3 / 3,3으로 갈 수 있다는 뜻으로 해석된다.

그러면 준규는 어디에서 왔을까?

저 위 식에 하나라도 만족하면 된다.

아마 1,2가 아닐까? 1,2같은 경우는 첫번째 식에 적용된다.

이런식으로 계산하면 (1,2) // (2,1) // (1,1)에서 왔다는 것을 예측할 수 있다.

 

문제는 최대값을 구하는 문제다.

그렇기 때문에 저 값들중에서 가장 큰 값을 준규가 가져가면 되지 않을까?

 

준규는 항상 최댓값만 가져가기 때문에 중복의 위험도 없어진다.

왜냐하면 항상 계산된 결과를 불러오기 때문이다.

 

위 식에서 mx가 중요한데..

만약, 이게 밖에 있으면 정상적으로 동작하지 않는다.ㅜㅜ;;

 

솔직히 dp는 어렵다.

한 가지 방법론이 있으면 또다른 방법이 있고,,ㅜㅜ;;

#include <stdio.h>
#include <algorithm>
using namespace std;
int D[1001][1001];
int candy[1001][1001];
int max3(int a, int b, int c) {
	return max(max(a, b), c);
}
int main(void) {
	int N, M;
	scanf("%d %d", &N, &M);
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++)
			scanf("%d", &candy[i][j]);
	}
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++)
			D[i][j] = max3(D[i - 1][j], D[i][j - 1], D[i - 1][j - 1]) + candy[i][j];		
	}
	printf("%d", D[N][M]);
}