[프로그래머스] 도둑질

문제

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

코딩테스트 연습 - 도둑질

문제해결방법

이 문제는 계단 오르기, 포도주 시식 과 비슷한 문제인데 원형으로 되어있다는 점이 달랐다.

그래서 첫번째 집과 마지막 집을 연속으로 털지 않도록 2가지 경우를 나눠서 계산해줬다.

1. 첫 번째 집을 터는 경우 : 이 경우에는 두 번째 집은 털 수 없으며, 마지막 집도 털 수 없다.

2. 첫 번째 집을 털지 않는 경우

코드

package Programmers;
 
public class solution_도둑질 {
    
    public static int solution(int[] money) {
        int answer = 0;
        int[][] DP = new int[2][money.length+1];
        DP[0][1] = money[0];
        for(int i=2; i<=money.length; i++) {
            if(i>2) DP[0][i] = Math.max(DP[0][i-2]+money[i-1], DP[0][i-1]);
            else DP[0][i] = DP[0][i-1];
            DP[1][i] = Math.max(DP[1][i-2]+money[i-1], DP[1][i-1]);
        }
        answer = Math.max(DP[0][money.length-1], DP[1][money.length]);
        return answer;
    }
    
    public static void main(String[] args) {
        int[] money = {1, 2, 3, 1};
        System.out.println(solution(money));
    }
}

코드에 대한 피드백이나 더 좋은 아이디어는 언제나 환영입니다.