금광

이것이 코딩테스트다 p.375

문제

nxm 크기의 금광
채굴자는 첫 번째 열에서부터 금을 캐기 시작
m번에 걸쳐 매번 오른쪽 위, 오른쪽, 오른쪽 아래 방향으로 이동

입력

첫 번째 줄에 테스트 케이스 T (1<=T<=1000)
n, m이 공백으로 구분되어 입력 (1<=n,m<=20)
nxm개의 금의 개수가 공백으로 입력

출력

테스트 케이스마다 채굴자가 얻을 수 있는 금의 최대 크기

풀이

• 세로 방향으로 진행되는 경로의 최대 크기 문제(백준 1932번 정수 삼각형) 와 비슷하지만 이번에는 가로 방향으로 진행
• 맨 윗줄과 아랫줄의 진행방향은 두 방향만 가능하다는점 유의
• 각 경로에 있어서 최대값으로 갱신

using namespace std;

vector<int> arr;
int main(){
    int test, n,m;
    cin>>test;
    
    for(int t=0;t < test; t++){
        cin>>n>>m;
        int arr[401]={0, }; //1차원배열로 금의 수 입력됨
        for(int i=0;i < n*m; i++){
            cin>>arr[i];
        }
        
        int v[21][21];
        int index=0;
        
        for(int i=0;i<n;i++){ //2차원 배열로 재배열
            for(int j=0;j<m;j++){
                v[i][j]=arr[index++];
            }
        }
        for(int j=1;j<m;j++){
            for(int i=0;i<n;i++){
                if(i==0){ //맨 윗줄인 경우 -> 오른쪽, 오른쪽아래방향
                    v[i][j]+=max(v[i][j-1],v[i+1][j-1]);
                }
                else if(i==n-1){//맨 밑줄 경우 -> 오른쪽, 오른쪽윗방향
                    v[i][j]+=max(v[i][j-1],v[i-1][j-1]);
                }else{ //가운데 -> 3방향으로 갈 수 있는 경우
                    int temp=max(v[i][j-1],v[i+1][j-1]);
                    temp=max(temp,v[i-1][j-1]);
                    v[i][j]+=temp;
                }
            }
        }
        
        int maxResult=0;
        for(int i=0;i<n;i++){
            maxResult=max(maxResult, v[i][m-1]);
        }
        cout<<maxResult<<"\n";
    }
}

• 결과