[하한문] 프로그래머스 - 땅따먹기

문제 설명

 

땅따먹기 게임을 하려고 합니다. 땅따먹기 게임의 땅(land)은 총 N행 4열로 이루어져 있고, 모든 칸에는 점수가 쓰여 있습니다. 1행부터 땅을 밟으며 한 행씩 내려올 때, 각 행의 4칸 중 한 칸만 밟으면서 내려와야 합니다. 단, 땅따먹기 게임에는 한 행씩 내려올 때, 같은 열을 연속해서 밟을 수 없는 특수 규칙이 있습니다.

 

예를 들면,

 

| 1 | 2 | 3 | 5 |

| 5 | 6 | 7 | 8 |

| 4 | 3 | 2 | 1 |

 

로 땅이 주어졌다면, 1행에서 네번째 칸 (5)를 밟았으면, 2행의 네번째 칸 (8)은 밟을 수 없습니다.

마지막 행까지 모두 내려왔을 때, 얻을 수 있는 점수의 최대값을 return하는 solution 함수를 완성해 주세요. 위 예의 경우, 1행의 네번째 칸 (5), 2행의 세번째 칸 (7), 3행의 첫번째 칸 (4) 땅을 밟아 16점이 최고점이 되므로 16을 return 하면 됩니다.

 

 

 

요즘도 dfs를 열심히 공부중이라 재귀를 통해서 완전 탐색을 시도했다.

N을 land size로 받아서 마지막으로 answer에 모든 경우의수를 더한 값중에 가장큰 sum을 담았다.

하지만 테스트는 통과하나 시간초과. 이거는 피보나치를 재귀 식으로 풀었을 때랑 같은 경우다.

굳이 돌아도 되지 않은 경우 생각해서 다 돌아댕기니까 시간이 너무 오래걸리는거다.

int answer =0;
int N= 0;
void dfs(vector<vector<int> > land,int y,int sum,int no_ac){
    if(y>=N){
        if(sum>answer){
            answer = sum;
        }
        return ;
    }
    for(int i =0 ; i<4;i++){
        if(no_ac == i) {continue;}        
        sum += land[y][i];
        dfs(land,y+1,sum,i);
        sum -= land[y][i];
    }
}

 

그래서 계속 생각해 보다가 다이나믹 프로그래밍으로 풀어보았다.

D라는 2차원 배열에 계속해서 최댓값을 담아 넣는다,연속하지는 않게끔.

그리고 배열의 맨 마지막에 도착했을때의 최댓값들이 담겨 있을 것이다. 그 중 가장 큰놈을 고르면 된다.

int solution(vector<vector<int> > land)
{
     const int  N= land.size();
    // dfs(land,0,0,-1);
    for(int i=0; i<4; i++){
        D[0][i] = land[0][i];
    }
    // dp로 풀어야 시간이 나옴
    for(int i=1; i<N; i++){
        for(int j=0;j<4; j++){
            for(int k=0; k<4;k++){
                if( j != k){
                    if(land[i][j]+D[i-1][k]> D[i][j]){
                        D[i][j] =land[i][j]+D[i-1][k];   
                    }
                }
            }
        }
    }
    int max =0;
    for(int i =0; i<4; i++){
        max = D[N-1][i]> max ? D[N-1][i]: max;
    }
    
    return max;
}

 

 

출처 - 프로그래머스