[프로그래머스] 도둑질

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

프로그래머스

🤔 문제분석

첫번째 집을 방문하거나, 첫번째 집을 방문하지 않는경우를 분기시켜 최대값을 구하면 된다.

• 첫번째 집을 방문한경우는 마지막 집을 방문할 수 없다.
• 첫번째 집을 방문하지않는 경우는 마지막 집을 방문할 수 있다.
• i번째의 최대값을 구할때 2가지의 값중 최대값을 갱신시켜준다.
  • i-2 번째에서 온경우 자기자신이 방문 가능함 dp[i-2] + money[i]
  • i-1 번째에서 온경우 자기자신이 방문 불가능 함으로 dp[i-1]
  • 따라서 점화식은 dp[i] = max(dp[i-2]+mondy[i], dp[i-1]) 로 나타낼 수 있다.

dp 배열을 사용하지않고 ( 메모리 효율 최대화 ) temp 변수를 2개 두어서 prev1(i-1) prev2(i-2) 를 두어서 문제를 해결하였습니다.

💻 코드

// <https://school.programmers.co.kr/learn/courses/30/lessons/42897>
class Solution {
    public int solution(int[] money) {
        int n = money.length;
        if (n == 1) return money[0];
        int prev1 = money[0], prev2 = 0;
        int includeFirst = 0, excludeFirst = 0;

        // 첫 번째 집을 포함하는 경우: 마지막 집은 털 수 없음
        for (int i = 1; i < n - 1; i++) {
            includeFirst = Math.max(prev1, prev2 + money[i]);
            prev2 = prev1;
            prev1 = includeFirst;
        }
        includeFirst = prev1;

        // 첫 번째 집을 제외하는 경우: 마지막 집을 털 수 있음
        prev1 = money[1];  // 두 번째 집부터 시작
        prev2 = 0;
        for (int i = 2; i < n; i++) {
            excludeFirst = Math.max(prev1, prev2 + money[i]);
            prev2 = prev1;
            prev1 = excludeFirst;
        }
        excludeFirst = prev1;

        return Math.max(includeFirst, excludeFirst);
    }
}