[프로그래머스/JAVA] 고득점Kit > 동적계획법(Dynamic Programming) > 도둑질 (by 다알쥐AI)

틱톡라이트 초대링크 https://lite.tiktok.com/t/ZSjqX7SfC/

[기간 한정] 보는 재미로, 버는 재미로! 영상만 봐도, 좋아요만 눌러도, 검색만 해도, 포인트가 차

[도둑질] 고득점Kit > 동적계획법(Dynamic Programming) > 도둑질

 
 
※ 주의 : 문제풀이 방법은 다양합니다. 참고만 해주세요 ※
[문제설명]

도둑이 어느 마을을 털 계획을 하고 있습니다. 이 마을의 모든 집들은 아래 그림과 같이 동그랗게 배치되어 있습니다.

각 집들은 서로 인접한 집들과 방범장치가 연결되어 있기 때문에 인접한 두 집을 털면 경보가 울립니다.

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

 

제한사항

• 이 마을에 있는 집은 3개 이상 1,000,000개 이하입니다.
• money 배열의 각 원소는 0 이상 1,000 이하인 정수입니다.

입출력 예

---

[간단설명]
도둑이 연속된 집이 아닌 돈을 훔칠 때, 돈의 최대값 구하기
 
[접근방법]
1. 첫번째 집을 포함하는 경우, 배열을 만들고 값을 초기화 한다.
2. 마지막 집을 포함하는 경우, 배열을 만들고 값을 초기화 한다.
3. 각각 (2번째전 + 현재위치), (이전위치) 값의 최대값을 현재위치에 저장한다.
ㄴ> 동적계획법(Dynamic Programming)
4. 두 배열중 더 큰 숫자를 리턴한다.
 
[주의사항]
배열을 초기화 할때, 0번째 인덱스 값에 0을 넣어주자.
ㄴ> 1번째, 2번째 값을 DP 점화식으로 비교해야하기 때문에
 
[소스공개]

class Solution {
    public int solution(int[] money) {
       
        // 처음 집이 포함일때
        int[] first = new int[money.length+1];
        // 마지막 집이 포함일때 
        int[] last = new int[money.length+1];
        
        // 0번째 배열에 0을 넣어준다 
        // dp 점화식에 0이 없으면, 1번째, 2번째 숫자를 비교할 수 없다 
        first[0]=0;
        last[0]=0;
        
        // 1번째 배열부터 값을 넣어준다
        // first : money 마지막값 제외
        // last : money 처음값 제외 
        for(int i=0;i<money.length-1;i++){
            first[i+1]=money[i];
            last[i+1]=money[i+1];
        }
        
        // 2번째 배열부터 max 값찾기
        // 1) 2번째 전 위치 값 + 현재 위치 값
        // 2) 직전 위치 값
        // 처음 집 포함일 경우, 마지막 집 포함일 경우 둘다 계산 
        for(int i=2;i<first.length;i++){
            first[i]=Math.max(first[i-2]+first[i], first[i-1]);
             last[i]=Math.max(last[i-2]+last[i], last[i-1]);
        }
       
        // 처음 집, 마지막 집 결과중 최대값 리턴 
        return Math.max(first[money.length],last[money.length]);
    }
}

 
[실행결과]