Menu

Subscribe

[JAVA/프로그래머스] 동적계획법(Dynamic Programming)_도둑질

HEESOO on Programmers

👀 문제

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

👊 도전

1. 설계

  1. 첫 번째 집을 훔치는 것과 아닌 것에 따라 값이 달라진다.
  2. 두 경우에 따른 값을 저장할 배열을 두개 생성한다.
  3. 현재 집의 돈을 훔치는게 이득인지 체크한다.

2. 구현 (성공 코드)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

/**
 *
 * @author HEESOO
 *
 */
 class Solution {
     public int solution(int[] money) {
         int answer = 0;
         int[] dp=new int[money.length-1];//마지막은 훔칠 수 없으므로 -1
         int[] dp2=new int[money.length];

         //dp 첫 번째 집을 훔치는 경우
         dp[0]=money[0];
         dp[1]=money[0];//0번째 집을 훔쳤으므로 1번은 훔칠 수 없으므로 현재까지의 최댓값(dp[0])을 저장
         for(int i=2;i<dp.length;i++){
             dp[i]=Math.max(dp[i-2]+money[i], dp[i-1]);
         }

         //dp2 두 번쨰 집부터 훔치는 경우
         dp2[1]=money[1];
         for(int i=2;i<dp2.length;i++){
             dp2[i]=Math.max(dp2[i-2]+money[i], dp2[i-1]);
         }

         answer=Math.max(dp[dp.length-1], dp2[dp2.length-1]);
         return answer;
     }
 }

3. 결과

실행결과 🤟 성공 🤟

4. 설명

  1. 경우의 수는 두 개이다.
    • 첫 번째 집을 훔치는 경우(dp), 두 번째 집부터 훔치는 경우(dp2)로 나뉜다.
    • 첫 번째 집을 훔친다면 마지막은 훔칠 수 없으므로 배열의 크기는 money.length-1이다.
  2. 돈을 훔칠지 말지 결정한다.
    • 훔칠 수 있다면 dp[i-2]+money[i]이다(한 단계 건너뛰고 훔칠 수 있으므로). 지금 훔친다면 dp[i-1]의 값은 사용할 수 없다.
    • 따라서 dp[i-2]+money[i]>dp[i-1]라면 훔치고, 아니라면 훔치지 않는다.
    • 훔치지 않는다면 다음에서 dp[i-1]값을 사용한다는 뜻이다.

👏 해결 완료!

처음에는 집을 기준으로 한 번 건너뛸지 두 번 할지에 따라서 코드를 작성할까 했는데, 돈을 기준으로 코드를 구상하면 더 깔끔하고 좋은 것 같다. 근데 그 생각의 전환이 어렵다.

참고