백준 BOJ 2169 - 로봇 조종하기

2차원 배열에서의 Dp는 너무 어려운 거 같다 ㅠ

익숙해질때까지 많이 풀어봐야겠다....

​

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

2169번: 로봇 조종하기

문제 풀때에 있어 굉장히 어려운 부분이 한군데 있었다.

​

5 5

10 25 7 8 13

68 24 -78 63 32

12 -69 100 -29 -25

-16 -22 -57 -33 99

7 -76 -11 77 15

​

테스트케이스에 입력이 이렇게 들어오는데

두번째 줄 첫번째 입력인 68의 경우

단순히 작성하면 78으로 결과가 나오겠지만

실제로는 10 -> 25 -> 24 -> 68 이라는 경로를 지나갈 때 최대값이 나오게 될 것이다.

단순히 작성한경우

68을 계산할때 24에 있는 최대값을 아직 계산하지 않아 볼 수 없기 때문에

왼쪽으로 더해가며 계산 한번, 오른쪽으로 더해가며 계산을 한번

이렇게 두번 해줘서 비교해줬다.

#include <stdio.h>

int max(int a, int b){ return a>b?a:b; }

int n,m;
int input[1001][1001] = {0};
int dp[1001][1001]	  = {0};
int tmpr[1001] 	      = {0};
int tmpl[1001] 	      = {0};

int main(){
	scanf("%d %d", &n, &m);
	for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) scanf("%d", &input[i][j]);
	
	dp[1][1] = input[1][1];
	for(int i=2; i<=m; i++) dp[1][i] += input[1][i] + dp[1][i-1];
	
	for(int i=2; i<=n; i++){
		tmpr[0] =   dp[i-1][1];
		tmpl[m+1] = dp[i-1][m];
		for(int j=1; j<=m; j++) tmpr[j] = max(tmpr[j-1], dp[i-1][j]) + input[i][j];
		for(int j=m; j>=1; j--) tmpl[j] = max(tmpl[j+1], dp[i-1][j]) + input[i][j];
		
		for(int j=1; j<=m; j++) dp[i][j] = max(tmpr[j], tmpl[j]);
	}
	printf("%d\n", dp[n][m]);
	return 0;
}

dp[i][j]는 로봇이 i, j위치에 있을때의 가치의 최댓값이다.

위에서 말한 문제를 해결하기 위해

오른쪽값과 위의 값을 비교하는 tmpr(tmp-righ)이라는 배열과

왼쪽값과 위의 값을 비교하는 tmpl(tmp-left)이라는 배열

두가지를 만들어 각각을 계산하고,

dp[i][j]에는 둘 중의 최대값을 채워넣었다.

이렇게 하면 진짜 최대값을 dp 배열에 집어넣을 수 있게 된다.

​

그런데 첫번째 줄의 입력에 대해서는 무조건 1,1에서 시작함이 보장되므로

왼쪽값을 비교할 필요가 없다.

그래서 따로 빼서 계산해줬다.

​

우리가 원하는건 로봇이 n,m위치에 있을때의 가치의 최대값이므로

dp[n][m]을 출력해주면 AC.

​