[DP] 도둑질 - JAVA

[문제]

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

프로그래머스

---

예전에 비슷한 문제를 풀어본 기억이 있어서 초기 아이디어는 금방 얻을 수 있었다

근데 뒤에서 생각이 좀 꼬여서 초기 코드는 꽤나 지저분하다,,,

그래도 일단 초기 내 생각을 간단하게나마 정리해보고, 개선된 코드도 뒤에 소개를 해보도록 하겠다!

 

🤔 DP 배열 정의

먼저 문제에 접근하는 아이디어는 첫집을 터는 경우와 털지 않는 경우로 구분하는 것이다!

• 첫집을 터는 경우 → 막집을 털 수 없다
• 첫집을 털지 않지 않는 경우 → 막집을 털 수 있다

 

이 문제에서 마을은 원형 구조로 되어있기 때문에 위와 같이 경우를 나눠서 생각해줘야 한다!

그래서 첫집을 터는 경우의 dp 배열은 dpO, 첫집을 털지 않는 경우의 배열은 dpX로 명명하였다

 

 

🤔 점화식 정의

각 경우에서 최댓값을 어떻게 정의할 수 있을까 고민하다가 생각한 점화식은 다음과 같다

dp[i] = money[i] + Math.max(dp[i-2], dp[i-3]);

?? : 이게 뭐죠..

 

이래서 dp 문제는 배열에 저장되는 값을 정의하는 게 굉장히 중요하다..^_ㅠ

나는 여기서 dp[n]은 n번째 집을 무조건 턴다고 했을 때의 최댓값을 저장해주었다

 

그러면 2가지 경우가 존재한다

• 현재 집을 털고, 앞앞집을 터는 경우 → money[i] + dp[i-2]
• 현재 집을 털고, 앞앞앞집을 터는 경우 → money[i] + dp[i-3]

 

그래서 점화식이 저렇게 나온 것이다

ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

아마 여기서부터 내 사고회로가 고장나기 시작한 것 같다🤖

 

 

🤔 answer 정의

점화식이 복잡한 만큼 answer를 구하기 위한 분기조건도 상당히 까다롭다,,

dpO에서의 최댓값과 dpX에서의 최댓값을 먼저 구하고, 이 2개의 값 중 최댓값이 answer가 된다

dpO는 뒤에서 2번째나 3번째 값이 최댓값이 된다

dpX는 뒤에서 1번째나 2번째 값이 최댓값이 된다

음… 아무튼 최종 코드는 다음과 같았따..

 

 

😅 개선 전 최종 코드

class Solution {
    public int solution(int[] money) {
        int answer = 0;
        int[] dpO = new int[money.length]; //첫집, 짝수
        int[] dpX = new int[money.length]; //막집, 홀수
        int len = money.length;

        dpO[0] = money[0];
        dpO[1] = 0;
        dpO[2] = dpO[0] + money[2];

        dpX[0] = 0;
        dpX[1] = money[1];
        dpX[2] = money[2];

        for(int i=3;i<len-1;i++) {
            dpO[i] = money[i] + Math.max(dpO[i-2], dpO[i-3]);
            dpX[i] = money[i] + Math.max(dpX[i-2], dpX[i-3]);
        }
        dpX[len-1] = money[len-1] + Math.max(dpX[len-3], dpX[len-4]);

        int first = Math.max(dpO[len-2], dpO[len-3]);
        int second = Math.max(dpX[len-1], dpX[len-2]);
        answer = Math.max(first, second);
        return answer;
    }
}

확실히 분기 조건이 많고 점화식도 깔끔하지 않은 느낌이 난다..ㅠ

근데 로직 자체는 오류가 없다보니 시험삼아 제출한 코드가 고대로 통과해버렸다…😳

 

---

이게 되겠어~? 하고 제출한 위의 코드는 고대로 성공해버렸고,,, 찜찜해진 나는 다른 사람의 풀이를 보았다

거기서 이차원 배열을 통해 깔끔하게 해결한 코드를 보았다

나처럼 다양한 경우의 수를 고려해서 answer를 구할 필요 없이, 우선은 반복문으로 끝까지 구하고 나중에 경우를 빼주면 되는 것이었다..!

자 이게 무슨 얘기인지 차근차근 접근해보자!

 

😇 DP 배열 정의

먼저, 문제에 접근하는 아이디어는 동일하다

• 첫집을 터는 경우 (막집X)
• 첫집을 털지 않지 않는 경우 (막집O)

따라서 초기 아이디어와 동일하게 첫집을 터는 경우의 배열은 dpO, 첫집을 털지 않는 경우의 배열은 dpX로 설정했다

 

 

😇 최댓값을 구하는 점화식 정의

점화식 정의 부분에서 약간 달라지게 된다

초기 아이디어에서는 dp[n]은 n번째 집을 무조건 털 때의 최댓값을 저장하는 경우였다

그래서 마지막에 answer를 구하는 부분에서 분기 조건이 많이 발생한 것이다!

 

따라서 dp[n]에 저장되는 값의 정의를 바꿔줘서 마지막 부분의 분기 조건을 줄여주었다

dp[n]에는 그냥 n번째 집까지 도둑이 털 수 있는 최댓값을 저장해주면 된다

그러면 어떻게 되느냐~

 

dp[n]에 저장될 수 있는 최댓값은 2가지가 존재한다

• 현재 집을 털고, 앞앞집을 터는 경우 → money[i] + dp[i-2]
• 현재 집을 털지 않는 경우(= 앞집의 최댓값과 동일) → dp[i-1]

쉽게 말해서 현재 집을 털었을 때와 털지 않았을 때로 나눠서 최댓값을 구하면 되는것이다!

(도둑질은 집을 연달아서 할 수 없다는 조건을 이용한것이다😋 )

dp[i] = Math.max(money[i]+dp[i-2], dp[i-1]);

 

 

😇 answer를 결정하는 방법

위의 점화식을 통해서 값을 구하게 되면 최종적으로 dp 배열의 마지막 원소에 최댓값이 저장될 것이다

이 때 조심해야 할 부분이 있다!

 

바로 첫집을 턴 경우인 dpO 배열이다

이의 경우에는 첫집을 털었으니까 마지막 집은 털 수가 없다!

그런데 dpO 배열의 마지막 원소에는 마지막 집을 턴 경우가 저장될 수도 있기 때문에 가능한 최댓값은 dpO의 배열 원소에서 뒤에서 2번째 원소가 될 것이다!

 

dpX는 첫집을 털지 않았으므로 막집을 털어도 상관없어서 그냥 마지막 원소가 최댓값이 된다~

따라서 점화식은 다음과 같이 구할 수 있다

answer = Math.max(dpO[len-2], dpX[len-1]);

 

😇 최종 코드

최종적으로 개선한 코드는 다음과 같다!

class Solution {
    public int solution(int[] money) {
        int[] dpO = new int[money.length]; //첫집O
        int[] dpX = new int[money.length]; //첫집X
        int len = money.length;

        dpO[0] = money[0];
        dpO[1] = money[0];

        dpX[0] = 0;
        dpX[1] = money[1];

        for (int i = 2; i < len; i++) {
			//현재 집을 털지 않는 경우 vs 현재 집을 터는 경우
            dpO[i] = Math.max(dpO[i - 1], money[i] + dpO[i - 2]);
            dpX[i] = Math.max(dpX[i - 1], money[i] + dpX[i - 2]);
        }

		//첫집을 터는 경우, 막집은 못터니까 dpO[len-2]까지만 가능하다
        return Math.max(dpO[len - 2], dpX[len - 1]);
    }
}

확실히 분기가 적어지고 점화식도 깔끔해져서 로직이 정리된 느낌이다!

오늘도 알고리즘 문제 해결 완료 🤓