[도전 18일차] 로봇 조종하기 - KOI 고등부 풀이

※복습 : 

 

문제 : BOJ 2169 로봇 조종하기

문제 링크

 

사용 알고리즘 : DP

풀이: 

DP에 오는 방향 정보를 포함하자. 로봇은 왼쪽, 아래쪽, 오른쪽으로만 이동할 수 있으므로 

오는 방향은 오른쪽 , 위쪽, 왼쪽이다. 유의할 점은 오른쪽 방향 DT를 채울 때는 오른쪽에서부터 채우고,

왼쪽 방향 DT를 채울 때는 왼쪽에서부터 채워야 한다.

 

초기화 조건이 살짝 까다로운데 이는 직접 코드로 짜보는 수밖에 없다.

역시 미리 체계적으로 정해놓고 가면 디버깅이 빠르다.

 

DT 정의

DT[i][j][k] =로봇이 k방향 ( 0:위쪽,1:왼쪽,2:오른쪽)에서  (i,j)에 도착할 때까지 얻을 수 있는 가치의 최대합.

DT 관계식

$$DT[i][j][0]=max({DT[i-1][j][0],DT[i-1][j][1],DT[i-1][j][2]})+arr[i][j];$$
$$DT[i][j][1]=max(DT[i][j-1][0],DT[i][j-1][1])+arr[i][j]; $$
$$DT[i][j][2]=max(DT[i][j+1][0],DT[i][j+1][2])+arr[i][j];$$

코드의 DT 초기화 부분을 공부하면 DP 실력이 늘 가능성이 높다!

코드 

//pentagon@sasa.hs.kr 
#include<bits/stdc++.h>
#define vsort(v) sort(v.begin(),v.end())
#define fastIO ios::sync_with_stdio(false);cin.tie(0);
const int INF = 1e9;
using namespace std;
int n,m,arr[1010][1010],DT[1010][1010][3]; // 오는방향은  0:위쪽, 1: 왼쪽, 2:오른쪽 
void input(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>arr[i][j];
}
void solve(){
    DT[1][1][0]=DT[1][1][1]=arr[1][1];
    for(int i=2;i<=m;i++)
        DT[1][i][1]=DT[1][i-1][1]+arr[1][i];
    for(int i=m;i>=1;i--)
        DT[1][i][2]=DT[1][i][0]=-INF;
    for(int i=2,k;i<=n;i++){
        for(int j=1;j<=m;j++)
                DT[i][j][0]=max({DT[i-1][j][0],DT[i-1][j][1],DT[i-1][j][2]})+arr[i][j];
        DT[i][1][1]=-INF;
        for(int j=2;j<=m;j++)
            DT[i][j][1]=max(DT[i][j-1][0],DT[i][j-1][1])+arr[i][j];
        DT[i][m][2]=-INF;
        for(int j=m-1;j>=1;j--)
            DT[i][j][2]=max(DT[i][j+1][0],DT[i][j+1][2])+arr[i][j];
    }
    cout<<max(DT[n][m][0],DT[n][m][1]);
}
int main(){
    fastIO;
    input();
    solve();
}

 

궁금한 점이 있으시다면 질문 남겨주세요 :)