99클럽 코테 스터디 41일차 TIL / [프로그래머스] 도둑질

오늘의 학습 키워드

---

DP

문제

---

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

• 플랫폼: 프로그래머스
• 문제명: 도둑질
• 난이도: Lv4

풀이

---

class Solution {
    public int solution(int[] money) {
        int n = money.length;
        int[] firstO = new int[n];
        int[] firstX = new int[n];
        firstO[1] = firstO[0] = money[0];
        firstX[1] = money[1];
        
        for(int i=2; i<n-1; i++) {
            firstO[i] = Math.max(firstO[i-1], firstO[i-2] + money[i]);
        }
        
        for(int i=2; i<n; i++) {
            firstX[i] = Math.max(firstX[i-1], firstX[i-2] + money[i]);
        }
        
        return Math.max(firstO[n - 2], firstX[n - 1]);
    }
}

접근

• 점화식 자체는 쉽게 도출할 수 있지만, 이웃된 집을 털 수 없다는 특징에 유의해야 하는 문제였습니다.
  • 점화식: Math.max(현재 집을 털지 않는 경우, 현재 집을 터는 경우)
• 그러나 위처럼 진행하게 될 경우 첫 번째와 마지막 집을 동시에 턴 경우를 예외처리하기 어렵습니다.
• 따라서, 시작부터 첫 번째 집을 터는 경우와 그렇지 않은 경우 두 가지로 나누어서 계산을 해줍니다.

  int[] firstO = new int[n];
  int[] firstX = new int[n];

• 그리고 첫 번째 집을 턴 경우에는 마지막 집을 털지 않도록 합니다.

  for(int i=2; i<n-1; i++) {
      firstO[i] = Math.max(firstO[i-1], firstO[i-2] + money[i]);
  }

• 그렇게 구해진 두 배열의 최댓값을 비교하여 리턴합니다.

소요 시간

40분