[프로그래머스/Lv.2] 땅따먹기

 

https://school.programmers.co.kr/learn/courses/30/lessons/12913#

프로그래머스

 

 

처음 접근할 때는 너무 단순하게 생각했었다

import java.util.*;

class Solution {
    static boolean[] check = new boolean[4];
    static int answer;
    static int max;
        
    int solution(int[][] land) {

        game(0, land);

        return answer;
    }
    
    void game(int x, int[][] land) {
        
        max = -1;
        
        for(int i = 0; i < 4; i++) {
            if(check[i] != true) { // 이전 행에서 방문하지 않은 열만 포함시키기
                max = Math.max(max, land[x][i]);         
            }
        }
        answer += max;
        check = new boolean[4];
        
        for(int i = 0; i < 4; i++) {
            if(land[x][i] == max) check[i] = true;
        }
        
        x++;
        if(x == land.length) return;
        else game(x, land);
        
    }
}

 

시작 행에서 최대값을 구하고 visited를 표시해준 후 다음 행에서는 visited가 표시되지 않은 열 안에서 최대값을 구하고 또 다음으로 넘어가고,,, 반복반복이었다

당연히 테스트케이스는 통과였지만 채점으로 넘어가자마자 모두 틀렸다

 

조금 더 넓게 생각해야하는거였다

만약 첫번째 행에서 최대값이 4열이었는데 다음 행에서 4열이 어마어마하게 큰 값이라면 이걸 놓쳐버리는거다 

 

검색해보니 dp로 풀어야 괜찮은 문제라고 하는데 아직 완벽하게 공부하지 못한 알고리즘이라 두려움이 앞섰다 그래서 어떤식으로 접근해야하는지 여러 글을 읽어봤고 아주 사아아아알짝 알거같아서 풀어봤다

 

class Solution {
    int solution(int[][] land) {
        int answer = 0;

        for(int i = 1; i < land.length; i++) {
            for(int j = 0; j < 4; j++) {
                int max = -1;
                
                for(int k = 0; k < 4; k++) {
                    if(j != k) max = Math.max(max, land[i-1][k]); // 같은 열이 아닌 열 중에 최대값
                }
                
                land[i][j] += max;            
            }
        }

        for(int i = 0; i < 4; i++) {
            
            answer = Math.max(answer, land[land.length-1][i]);
        }
        return answer;
    }
}

 

1	2	3	5
5	6	7	8
4	3	2	1

 

초기 land 배열은 이렇다 같은 열에 있는 값을 제외한 나머지 중에 최대값인 것을 전달받아 더해주며 배열을 바꿔줄거다

 

0행

1

2

3

5

-> 이전 행이 없으니 그대로  둔다

 

1행

1	2	3	5
5 + 5 = 10	6 + 5 = 11	7 + 5 = 12	8 + 3 = 11

-> 각각 이전 행에서 자기가 있는 열을 제외하고 최대값을 찾아 전달받고 더해주면 된다

 

2행

1	2	3	5
10	11	12	11
4 + 12 = 16	3 + 12 = 15	2 + 11 = 13	1 + 11 = 12

 

마지막 행까지 반복하면 되고 마지막 행의 값들 중 최대값을 찾아주면 정답이 된다!

 

 

 

통과는 했지만 완전히 내 머리로 푼건 아니기 때문에 앞으로 비슷한 문제를 많이 풀어보면서 dp 알고리즘 문제도 잘 대비해야겠다