땅따먹기

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

프로그래머스

 

Level 2 

 

행렬을 1개 씩 내려오면서 특정 조건을 만족하며 최대 점수를 구해야하는 문제

 

구현자체는 어렵지 않지만 아이디어를 짜는게 힘든 문제였다.

 

 

내가 고민한 방법은 DP 를 활용한 풀이 방식으로

현재 자신의 바로 위의 칸의 값을 제외한 즉 3개의 값 중 최대 값을 가져와

현재 자신의 값과 더해 한 줄 씩 내려올 때 마다 모든 칸이 최선의 경우를 유지하는 방법이다.

 

즉, 이렇게 될 경우 r 번째 행의 c 번 째 항목은

항상 자신이 수행할 수 있는 가장 최선의 방법으로 내려온 최대 값이 되며

최종적으로 나는 마지막 행의 4개의 원소들 중 최대 값만 반환해주면 되는 것이다.

말로는 굉장히 간단해 보이는데 장장 1시간 반을 굴린 결과다...

 

DP 문제가 코딩테스트에서 자주 나오지만 주제가 바뀔 때 마다 항상 까다롭다.

꾸준히 연습해야 할 것 같다.

 

import java.util.*;

public class Solution { //땅따먹기
    static int[][] map;

    public int solution(int[][] land) {
        map = land.clone();
        for(int idx = 0; idx < land.length-1; idx++){
            walkDown(idx+1, land[idx], land[idx+1]); //이전 행과 현재 행 사이 내려오는 작업
        }
        int answer = 0;
        for(int lastRowVal : land[land.length-1]){
            answer = Math.max(lastRowVal, answer); //최종적으로 마지막 행의 최대 값을 반환하기 위한 작업
        }
        return answer;
    }

    public void walkDown(int rowIdx, int[] currentRow, int[] nextRow){
        for(int nextIdx = 0; nextIdx < nextRow.length; nextIdx++){ //현재 행 탐색
            int currentMax = 0;
            for(int currentIdx = 0; currentIdx < currentRow.length; currentIdx++){ //이전 행 탐색
                if(nextIdx == currentIdx) //이전 행과 현재 행의 위치가 같은 원소는 배제
                    continue;
                currentMax = Math.max(currentMax, currentRow[currentIdx]); //위치가 같지 않은 원소들 중에서 최대 값을 추출
            }
            map[rowIdx][nextIdx] += currentMax; //현재 행의 원소에 이전 행에서 가져올 수 있는 최선의 최대 값을 엎어침 -> 다음 행 에서도 결과적으로 이전 행이 수행한 최선의 값을 넘겨줌
        }
    }
}