[프로그래머스] 도둑질

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

단순한 DP로 접근했다. 단지 끝과 끝이 연결되어 있는. 그래서 돈의 길이가 짝수 일때와 홀수일 때를 나눠서 계산했다.

def rob(money):
    dp = [0] * len(money)
    dp[0] = money[0]
    dp[1] = money[1]

    for i in range(2, len(money)):
        dp[i] = max(dp[i-2] + money[i], dp[i-1])
  
    return dp

def solution(money):
    # 점화식
    # dp[n] = max(dp[n-2] + money[n], dp[n-1])
    
    if len(money)%2:
        a = rob(money[:-1])
        b = rob(money[1:])
        return max(max(a), max(b))
    else:
        return max(rob(money))

rob라는 함수를 만들어서 이전 값을 기반으로 메모이제이션을 하는 로직을 저장했다. 그리고 홀수일 때는 각각 한쪽 끝이 없다는 가정을 하고 계산을 돌렸고 짝수는 그대로 했다. 그리고 실패했다.

[10, 5, 3, 1, 10]

실패한 테스트 케이스는 위와 같다. 계속 실패하길래 도저히 안 돼서 질문하기를 참고하니까 1번 테스트 케이스 실패한 사람의 댓글에 있었다. 정답은 15. 그러나 내 코드가 낸 답은 13이었다.
왼쪽 끝이 없다고 가정한 경우에서 첫번째 5가 2번 인덱스와 합쳐지게되고 결국 마지막 10과 함께 계산되는 경우가 없어지게 됐다.

그래서 혹시나해서

dp[i] = max(dp[i-2] + money[i], dp[i-1], dp[i-3] + money[i] if i >= 3 else 0)

i-3의 경우도 같이 계산해보게 했는데 그래도 통과 되지 않았다.

chat gpt한테 물어보니까

def rob_line(houses):
    n = len(houses)
    if n == 0:
        return 0
    if n == 1:
        return houses[0]
    
    dp = [0] * n
    dp[0] = houses[0]
    dp[1] = max(houses[0], houses[1])
    
    for i in range(2, n):
        dp[i] = max(dp[i-1], dp[i-2] + houses[i])
    
    return dp[-1]

def solution(money):
    if len(money) == 1:
        return money[0]
    if len(money) == 2:
        return max(money[0], money[1])
    
    # Case 1: Rob houses from the first to the second-to-last
    case1 = rob_line(money[:-1])
    # Case 2: Rob houses from the second to the last
    case2 = rob_line(money[1:])
    
    # The result is the maximum of the two cases
    return max(case1, case2)

위와 같이 코드를 만들어줬다. 내 코드의 문제점 중 첫 번째는 dp[1]을 money[1]로 고정한 것. dp[0]이 dp[1]보다 클 경우를 고려 해주지 않았다.
두번째는 짝수, 홀수 구분한 것. 짝수인 경우에 홀수 인덱스만 가져오고 짝수인덱스만 가져오고 이렇게 생각을 해서 중간에 꼬였을 경우에는 첫번째와 마지막이 동시에 존재하는 경우도 있게되는데 그거를 생각못했다. 그냥 전체다 한 쪽끝이 없는 경우를 두 번 계산해서 비교하면 되는 거였다.

def rob(money):
  dp = [0] * len(money)
  dp[0] = money[0]
  dp[1] = max(money[0], money[1])
  
  for i in range(2, len(money)):
    dp[i] = max(dp[i-2] + money[i], dp[i-1])
  
  return dp[-1]

def solution(money):
    # 점화식
    # dp[n] = max(dp[n-2] + money[n], dp[n-1])
    
    return max(rob(money[1:]), rob(money[:-1]))

그래서 다음과 같이 코드를 고쳤다. 그리고 통과했다.

Java

import java.util.*;

class Solution {
    public int solution(int[] money) {
        int left = robbing(Arrays.copyOfRange(money, 0, money.length-1));
        int right = robbing(Arrays.copyOfRange(money, 1, money.length));
        return Math.max(left, right);
    }
    
    public int robbing(int[] money){
        int[] rob = new int[money.length];
        rob[0] = money[0];
        rob[1] = Math.max(rob[0], money[1]);
        for (int i=2;i<money.length;i++){
            rob[i] = Math.max(money[i] + rob[i-2], rob[i-1]);
        }
        
        return rob[money.length-1];
    }
}