[프로그래머스] 도둑질

코딩테스트 연습 - 도둑질

모든 집들은 동그랗게 배치되어있다.

각 집들은 서로 인접한 집들과 방범장치가 연결되어있다 → 인접한 두 집을 털면 → 경보가 울린다.

각 집에 있는 돈이 담긴 배열 money가 주어질 때, 도둑이 훔칠 수 있는 돈의 최댓값을 리턴하도록 solution함수를 작성하라.

문제 이해하기

즉, 경보가 울리지 않고, 돈을 최대한 많이 털어야 한다는 말인것같다.

• 즉, 연속한 두 집은 선택할 수 없다. → i번째 집은 선택 → i+1은 선택할 수 없음.

• 그리고 또 중요한 것은, circular하다는 것이다. → 첫 번째 집을 선택했었다면, 마지막 집은 선택하면 안 된다. 따라서 나는 first라는 변수를 매 번 parameter로 넘겨주려고 한다.

  • 즉, first 집을 선택 했는가, 선택하지 않았는가의 경우를 나눠봐야한다고 생각했었다.

• i를 선택 → i+2부터를 고려해야한다. 근데 물론 i+2도 선택하지 않을수가 있다. 왜냐하면 i+3이 엄청 큰 수일 수도 있으니까 ⇒ 이런 전개가 나온다면 동적계획법이라고 생각했다.

---

문제를 풀어보자

틀린풀이1

여기서 first는 첫 번째 원소 선택 여부 정보를 담고있다.

• 현재를 선택: recur(i+2 , first)
• 현재를 선택x : recur(i+1, first)

len 이 집의 개수라고 하자. 마지막 집에 도달 한 경우, first선택 여부에 따라 달라진다.

• if( n == len && !first) → 이 경우는 이 n번째 원소도 선택하는게 허용이 되는데
• if(n == len && first ) → 이 경우는 return 0 을 해야함. 이 원소 를 선택하는게 허용되지 않기 때문이다.

dp[i] 는 [ i .. end ] 까지의 최댓값을 저장하도록 한다.

틀렸다 → dp를 2차원으로 변경 (하향식)→ 정확도테스트성공, 효율성런타임에러

첫 번째 집을 선택한 경우가 먼저 돌다 보니, 거기서 이미 dp값이 세팅이 되어버리면, 더 큰 값이 나오는 경우인 첫번재 집을 선택하지 않은 경우의 값이 업데이트가 안됨

그래서 dp를 2차원으로 변경하였다 → dp[i][first]

import java.util.*;
class Solution {
    public int len;
    public int[][] dp = new int[1000000][2];
    public int[] gmoney;
    public int solution(int[] money) {
        int answer = 0;
        gmoney = money;
        len = money.length;
        for(int i=0;i<len;i++)Arrays.fill(dp[i],-1);
        // 첫 번째 집을 선택 O 경우, 첫번째집을 선택 X 경우
        dp[0][1] = recur(2,1) + money[0];
        dp[0][0] = recur(1,0);
        
        answer = Math.max(dp[0][1],dp[0][0]);

            
        return answer;
    }
    public int recur(int n, int first){
        System.out.println("n :"+n+", first :"+first);
        // 선택할 수 없는 경우
        if(n==len-1 && first == 1)return 0; // 첫번째 집을 선택했었음 && n 이 마지막 집
        if(n >= len) return 0; // out of range
        // solved problem
        if(dp[n][first]!=-1)return dp[n][first];
        // n 번째 집을 선택하지 않는 경우, 선택하는 경우
        dp[n][first] = Math.max(recur(n+1,first),recur(n+2,first)+gmoney[n]);
        // System.out.println("n :"+n+", first :"+first+" --> 최대값 : "+dp[n]);
        return dp[n][first];
    }
    
}

성공 : 상향식

위의 풀이는 O(n)이긴 하지만 아마, O(2n)정도 될 것 같다.

아무튼 O(n)임에도 효율성에서 fail을 했다. 재귀함수를 호출해서 그런가?? 재귀적으로 풀면 확실히 시간이 오래 걸릴 수 밖에는 없지만.. 이 문제는 애초에 그런식으로는 풀지 말라고 낸 걸까?? 왜 그럴까.. ❓❓❓❓ 누가 좀 알려줬으면 좋겠다..

for문을 사용한 풀이로 변경해보자

현재 나의 경우는 재귀함수를 통해서 n이 len-1에 도달한 경우 → 여기서부터 재귀적으로 리턴해오는 것을 취하고 있었기 때문에 dp[i] = Math.max(dp[i+1],dp[i+2] +money[i]) 를 하고 있었다. ( i..end 가지의 최댓값)

하지만 이렇게 하지 않고 dp[i] = Math.max(dp[i-1], dp[i-2]+money[i] ) 도 얼마든지 가능하며 이것은 0.. i 까지 최대값을 담게 될 것이다.

• 그리고 여기서도, 첫 번째 집은 선택한 경우와 , 선택하지 않은 경우를 나누어서 풀어줘야한다.

import java.util.*;
class Solution {
    public int len;
    public int[][] dp = new int[1000000][2];
    public int[] gmoney;
    public int solution(int[] money) {
        int answer = 0;
        int i = 0;
        gmoney = money;
        len = money.length;
        for(i=0;i<len;i++)Arrays.fill(dp[i],-1);
        // dp[i][0] = Math.max(dp[i-1][0],dp[i-2][0]+money[i])
        dp[0][0] = 0; // 첫번째 집은 선택 x
        dp[1][0] = money[1]; // 첫번째 집을 선택 x , i가 1일 때 최댓값 
        dp[0][1] = money[0]; // 첫번째 집을 선택 o
        dp[1][1] = dp[0][1]; // 첫번째 집을 선택 o, i가 1일 때 최댓값
        // 문제조건이 집은 3개이상이라고 주어짐
        for(i=2;i<len-1;i++){
            dp[i][0] = Math.max(dp[i-2][0]+money[i] , dp[i-1][0]);
            dp[i][1] = Math.max(dp[i-2][1]+money[i] , dp[i-1][1]);
        }
        // i == n-1 일 때는, 첫 번째 집은 선택하지 않은 경우에 대해서만 업데이트 
        dp[i][0] = Math.max(dp[i-2][0]+money[i],dp[i-1][0]);
        dp[i][1] = Math.max(dp[i-2][1],dp[i-1][1]);
        answer = Math.max(dp[i][0],dp[i][1]);
        
            
        return answer;
    }

    
}