백준온라인 2169번 [로봇 조종하기][C++]

www.acmicpc.net/problem/2169

2169번: 로봇 조종하기

---

나의 풀이

 

  입력을 받은 배열의 i행 j열 값을  \(d [i][j]\) 라 하고 

  \(dp[i][j]\) 은 i행 j열 까지 왔을 경우 최대가치라 정의하자

 

   알고리즘은 다음과 같다

1. 로봇이 존재하는 0행을 기준으로는 오른쪽 밖에 가지 못하기 때문에 j가 커지는 순으로 \(dp [0][j]\)  = \(d [0][j]\) + \(dp [0][j-1]\) 식을 만족한다
2. 두 번째 행부터는 "0열에서 m열까지" 순차적으로 한 번 보고 "m열에서 0열까지" 거꾸로 총 두 번을 순회를 하면서
   첫 번째 행에서 썼던 방식과 비슷하게 \(dp [i][j]\) = max(위칸에서 얻을 수 최댓 값 , 이전칸에서 얻을수 있는 최댓값(순회 방향 기준)) + \(d [i][j]\) 현재 값을 해주면서 초기화해주면서 두 방식 중 최대의 값을 가지는 \(dp [i][j]\) 값을 최종적으로 저장해주면 된다.
3. \(d [n][m]\)에 답이 담긴다

 

탑다운 방식의 경우

dp배열 자체를 \(dp [i][j][방향]\)으로 둔 다음

1. 왼쪽, 오른쪽이 정 해지는 순간 계속 그 방향만을 봐야 하기 때문에 방향을 함수의 인자로 전달하여주고
2. 0,0 좌표까지 갔을 경우 반환 시작
3. 이동하는 게 가능한 좌표인지 판단하고 재귀 호출

---

코드

bottom-up

	#include <bits/stdc++.h>
	using namespace std;
	using vi = vector<int>;
	using vvi = vector<vi>;
	int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int n,m;
	cin>>n>>m;
	vvi d(n+1,vi(m+2));
	vvi l=d,r=d;
	for(int i=1;i<=n;i++){
	for(int j=1;j<=m;j++){
	cin>>d[i][j];
	}
	}
	for(int i=2;i<=m;i++)
	d[1][i]+=d[1][i-1];
	for(int i=2;i<=n;i++){
	r[i][1] = d[i-1][1]+d[i][1];
	for(int j=2;j<=m;j++){
	r[i][j] = max(r[i][j-1],d[i-1][j])+d[i][j];
	}
	l[i][m] = d[i-1][m]+d[i][m];
	for(int j=m-1;j>=0;j--){
	l[i][j] = max(l[i][j+1],d[i-1][j])+d[i][j];
	}
	for(int j=1;j<=m;j++){
	d[i][j] = max(r[i][j],l[i][j]);
	}
	}
	cout<<d[n][m];
	}

view raw .cpp hosted with ❤ by GitHub

top-down

	#include <bits/stdc++.h>
	#define INF 0x3f3f3f3f
	using namespace std;
	int d[1001][1001];
	int dp[1001][1001][3];
	int n,m;
	bool isPossible(int a,int b){
	if(a>=0&&a<n&&b>=0&&b<m)return true;
	return false;
	}
	int go(int r , int c , int dir){
	if(r==0&&c==0)
	return d[r][c];
	int &ret = dp[r][c][dir];
	if(ret!=-1)
	return ret;
	ret =-INF;
	if(isPossible(r-1,c))
	ret = max({ret,go(r-1,c,0),go(r-1,c,1),go(r-1,c,2)});
	if(isPossible(r,c-1)&&dir==1)
	ret = max(ret , go(r,c-1,dir));
	if(isPossible(r,c+1)&&dir==2)
	ret = max(ret , go(r,c+1,dir));
	return ret+=d[r][c];
	}
	int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	memset(dp,-1,sizeof(dp));
	cin>>n>>m;
	for(int i=0;i<n;i++){
	for(int j=0;j<m;j++){
	cin>>d[i][j];
	}
	}
	cout<<max(go(n-1,m-1,0),go(n-1,m-1,1));
	}

view raw .cpp hosted with ❤ by GitHub