땅따먹기 - 프로그래머스 (Java, Level 2)

 

https://www.acmicpc.net/blog/view/109

 

각 행에서 이전 행의 최댓값인 열을 제외한 나머지 3열 중 최댓값을 선택하면 될 줄 알았다.

 

하지만, 이전 행의 최댓값인 열과 현재 행의 최댓값인 열이 같을 경우,

이전 행의 선택을 바꾸는 것과 현재 행의 선택을 바꾸는 것은 총합의 차이를 가져온다.

즉, 현재의 선택이 매번 계속 다음 선택에 영향을 미친다.

 

그래서 다음 생각은 모든 경우를 고려하는 dfs를 생각했다.

하지만 행의 수가 100,000까지 가능했기 때문에 아니나 다를까 런타임 에러가 났다.

 

PriorityQueue<Integer> pq= new PriorityQueue<>(Collections.reverseOrder());
boolean[] isUsed = new boolean[4];
    
public int solution(int[][] land) {
    dfs(0, 0, land);
    return pq.peek();
}
public void dfs(int row, int sum, int[][] land) {
    if(row==land.length) {
        pq.add(sum);
        return;
    }//if end

    for(int i=0; i<4; i++) {
        if(!isUsed[i]) {
            sum += land[row][i];
            isUsed[i] = true;
            dfs(row+1, sum, land);
            sum -= land[row][i];
            isUsed[i] = false;
        }//if end
    }//for end
}//dfs() end

 

 

다른 블로그에서 Dynamic Programming을 활용해 간단하게 풀리는 것을 찾았다.

 

Dynamic Programming
큰 문제를, 반복되는 작은 문제로 나누어서 그 답을 저장하고 다시 큰 문제를 해결할 때 사용하는 방식이다.
(기억하기 프로그래밍)

조건
1) 동일한 작은 문제들이 반복하여 나타나는 경우 (Overlapping Subproblems)
2) 작은 문제의 최적값을 사용해 큰 문제의 최적값을 구할 수 있는 경우 (Optimal Substructure)

 

문제에 적용해보면,

각 행에서, 이전 행까지의 각 열의 최적값을 현재 행의 각 열과 더해 현재 행까지의 최적값을 구한다.

 

문제 속 예를 들어보면, 

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

문제의 조건인 해당 테이블을

 

1	2	3	4
10	11	12	11
16	15	13	13

로 바꿔주면 마지막 행의 최댓값인 16이 답이 된다.

 

public int solution(int[][] land) {
    int length = land.length;

    for(int i=1; i<length; i++) {
        land[i][0] += max(land[i-1][1], land[i-1][2], land[i-1][3]); 
        land[i][1] += max(land[i-1][0], land[i-1][2], land[i-1][3]); 
        land[i][2] += max(land[i-1][0], land[i-1][1], land[i-1][3]); 
        land[i][3] += max(land[i-1][0], land[i-1][1], land[i-1][2]); 
    }//for end

    return max(land[length-1]);
}//solution() end

//3요소 중 큰 수 리턴하는 메소드
public int max(int num1, int num2, int num3) {
    return Math.max(num1, Math.max(num2, num3));
}//max() end

//배열에서 가장 큰 요소 리턴하는 메소드
public int max(int[] numArr) {
    int max=0;
    for(int num : numArr) {
        if(max<num) max = num;
    }
    return max;
}//max() end

 

 

https://hongjw1938.tistory.com/47

https://shanepark.tistory.com/183