[11048] 이동하기, c++

[11048] 이동하기

 

www.acmicpc.net/problem/11048

11048번: 이동하기

한줄 후기 : ㅋㅋㅋㅋdp 극혐

 

포인트는 대각선은 사실 생각할 필요가 없다는 것

대각선으로 갈 바엔 가로 한번 세로 한번 가는게 더 이득임 캔디를 더 많이 모을 수 있으니까

#include <iostream>
using namespace std;
int miro[1001][1001];
int dp[1001][1001];
int main(){
	int n, m;
	cin >> n >> m;
	for(int i=1; i<=n; i++){
		for(int j=1; j<=m; j++){
			scanf("%d", &miro[i][j]);
			dp[i][j] = 0;
		}
	}

	for(int i=1; i<=n; i++){
		for(int j=1; j<=m; j++){
			dp[i][j] += max(dp[i-1][j], dp[i][j-1]);
			dp[i][j] += miro[i][j];
		}
	}
	cout << dp[n][m];
}

사실 처음에 이것도 재귀로 풀어야 하나 고민했는데 답이 안나오더라 그래서 그냥 반복문으로 풀었음.

재귀로 풀 수 있을지도?

dp[i][j] => 인덱스 i,j 에서 가질 수 있는 캔디 개수

문제에서 (r,c) -> (r+1,c) (r,c+1), (r+1,c+1) 이라 했는데 대각선 제외 하면 (r+1,c), (r,c+1) 만 비교하면 된다.

dp 배열을 이차원으로 만들어 준다.

처음에 생각 없이 dp[i+1][j], dp[i][j+1] 했는데 생각해보니 왔던 경로의 사탕을 저장해야하는데 저러고 있었음.

결과적으로 (r+1,c) (r,c+1) 이라는건 현재 입장에서 봤을 때 (r-1,c), (r,c-1) 을 지나 온 것이므로 그 사탕의 개수 중 최대 값을 더해주면 된다.

이때 dp값만 더하면 안되고, miro[][] 에 있는 현재 위치 캔디 수도 더해주자.

​