[프로그래머스] 도둑질 (Java)

카테고리

DP (동적계획법)

나만의 카테고리

간단한 DP

문제 링크

programmers.co.kr/learn/courses/30/lessons/42897?language=java

코딩테스트 연습 - 도둑질

요점

• 3번째 부터 뽑는 경우의 수를 생각해야한다

참고 지식

• Math.max()

풀이 (Java)

import java.util.*;

class Solution {
    public int solution(int[] money) {
        int answer = 0;
        
        int[] firstDp = new int[1000000];
        int[] secondDp = new int[1000000];
        
        firstDp[0] = money[0];
        firstDp[1] = money[0];
        
        int moneyLength = money.length;
        for (int index = 2; index < moneyLength - 1; index++) {
            firstDp[index] = Math.max(firstDp[index-2] + money[index], firstDp[index-1]);
        }
        
        secondDp[0] = 0;
        secondDp[1] = money[1];
        for (int index = 2; index < moneyLength; index++) {
            secondDp[index] = Math.max(secondDp[index-2] + money[index], secondDp[index-1]);
        }
        
        answer = Math.max(firstDp[moneyLength - 2], secondDp[moneyLength - 1]);
        
        return answer;
    }
}

 

---

알고리즘 초보가 정리한 글입니다

더 좋은 방법이나 코드에 대한 코멘트 언제나 환영합니다!