[Java] 도둑질

프로그래머스 문제

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

풀이 후기

1. 분석

첫 풀이에는 '그냥 홀수, 짝수 + 첫집과 마지막집이 이어지는 경우 아닌가?'라고 생각했는데 빠르게 틀렸다. 자세히 생각해보니 2칸 뛰는 것보다 3칸 뛰는 케이스가 있다는게 생각이 났다.

[999, 0, 0, 999, 1, 1, 1], 1999

2칸, 3칸, 4칸... 뛰는 모든 경우의 수를 계산할 수는 없으니 결국 DP문제였다.

2. 고치기

그래서 첫 시도에서는 다음과 같은 코드가 나왔다.

public class Solution {
    public int solution(int[] money) {
        int[] answer = new int[money.length];
        answer[0] = money[0];
        answer[1] = money[1];
        
        for(int i = 0; i < money.length; i++){
            if(i + 2 < money.length){
                answer[i + 2] = Math.max(answer[i + 2], answer[i] + money[i + 2]);
            }
            
            if(i + 3 < money.length){
                answer[i + 3] = Math.max(answer[i + 3], answer[i] + money[i + 3]);
            }
        }
        
        int one = answer[money.length - 2];
        int two = answer[money.length - 1];
        
        if(money.length % 2 == 1){
            int twoFirst = two - money[0];
            int twoLast = two - money[money.length - 1];
            return Math.max(one, Math.max(twoFirst, twoLast));
        }
        else{
            return Math.max(one, two);
        }
    }
}

이 코드의 핵심은 다른 얘가 너에게 준 값 vs 내가 들고 있는 값 + 네 값

그리고 그 값을 2칸, 3칸 앞에 전달해서 비교하는 것. 왜 2칸과 3칸이냐면 1칸은 갈 수가 없고, 4칸은 2칸에서 2칸 앞에 있기에, 넣을 필요가 없다. 아래는 엑셀로 계산해본 그거.

오픈 테케 + 직접 커스텀 테케 까지는 돌아갔으나, 히든 테케에서 문제가 되었다.

[1, 0, 0, 1, 0, 3]

홀수인 경우에만 첫번째와 마지막이 이어진다고 생각했는데, 요런 케이스가 또 존재했었음. 결국 AI와 싸우다가 첫번째 집 포함, 첫번째 집 미포함, 2개의 배열을 2개로 만들어야 한다는 것을 깨달았다. 결국 고치고 고쳐서 통과는 했다.

3. 실행 결과

4. 코드

public class Solution {
    public int solution(int[] money) {
        int[] first = new int[money.length];
        int[] second = new int[money.length];

        first[0] = money[0];
        first[1] = money[1];
        second[0] = 0;
        second[1] = money[1];
        
        for(int i = 0; i < money.length; i++){
            if(i + 2 < money.length){
                first[i + 2] = Math.max(first[i + 2], first[i] + money[i + 2]);
                second[i + 2] = Math.max(second[i + 2], second[i] + money[i + 2]);
            }
            
            if(i + 3 < money.length){
                first[i + 3] = Math.max(first[i + 3], first[i] + money[i + 3]);
                second[i + 3] = Math.max(second[i + 3], second[i] + money[i + 3]);
            }
        }
        
        int ff = Math.max(first[money.length - 2], first[money.length - 1] - money[money.length - 1]);
        return Math.max(ff, second[money.length - 1]);
    }
}

뭔가 좀 엉성한 코드지만 돌아가니까 만족.

근데 DP문제 너무 싫다...