❓문제설명
도둑질
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
🔍문제해석
어떤걸 풀어야 할까?
- 이렇게 원형으로 집들이 배치되어있을때, 도둑이 집을 털어 가장 많이 훔칠 수 있는 돈을 구하라.
- 단, 각 집들은 인접한 집들과 방범장치가 연결되어있기 때문에 두 집을 연달아서 털게 되면 경보가 울린다.
🧐문제풀이
- 문제 풀이 구상
https://school.programmers.co.kr/questions/12213
위 게시글의 힌트를 얻어 풀이를 생각해보았다.
원형으로 구성되어있는데 인접한 두 집은 털지 못하니,
1. 첫번째 집을 털고 마지막 집은 털지 않았을때
2. 첫번째 집을 털지않고 마지막 집은 털었을때
위 2개의 케이스에 대해서 dp를 적용하고, 두 개의 결과값 중 가장 큰 값을 정답으로 리턴한다.
- 알고리즘 선택
인접한 두 집을 털지 못한다는 건 현재 집을 털던지 아니면 그냥 가는지 두 개의 케이스를 계속 비교하여 더 큰 수를 계산해야 한다는 것이다.
결국 이전의 계산된 결과를 갖다 쓴다는 점에서 DP, 동적계획법을 선택했다.
!제출코드
- 첫번째 케이스 계산
- 첫 번째 집을 털고, 마지막 집을 털지 않는 경우 시작 => 1번 계산 시, 각 집까지 들렀을때 가장 많이 훔칠 수 있는 금액 담는 배열 생성
- 첫번째 집에서 훔친 돈을 첫번째 인덱스에 대입
- 첫번째 집만 털거나, 첫번째 집을 털지 않고 두번째 집을 털었을 때의 경우 중 더 큰 금액 대입
- 마지막 집은 제외하고 반복문 시작
- 해당 집을 털지 않거나, 터는 경우 중 더 큰 금액을 대입한다.
- 마지막 집 계산
- 두번째 케이스 계산,첫 번째 집을 털지 않고, 마지막 집을 터는 경우 시작 => 2번 계산 시, 각 집까지 들렀을때 가장 많이 훔칠 수 있는 금액 담는 배열 생성
- 두번째 집에서 훔친 돈을 두번째 인덱스에 대입
- 두번째 집만 털거나, 두번째 집을 털지 않고 세번째 집을 털었을 때의 경우 중 더 큰 금액 대입
- 마지막 집 까지 포함하고 반복문 시작
- 두 케이스 중 더 큰 값 리턴
import java.util.*;
class Solution {
public static int solution(int[] money) {
int n = money.length;
// (1) 첫 번째 집을 털고 마지막 집을 털지 않는 경우
// (2) 해당 집까지 털었을때 가장 많은 금액을 담는 배열
int[] dp1 = new int[n];
// (3)
dp1[0] = money[0];
// (4) 첫번째 집만 털거나, 첫번째 집을 털지 않고 두번째 집만 털었을때의 가장 큰 금액
dp1[1] = Math.max(money[0], money[1]);
// (5) 마지막 집은 털지 않기 때문에 제외
for (int i = 2; i < n -1 ; i++) {
// (6) 털지 않고 직전 금액 계승, 지지난 금액 + 현재 금액 더하면서 턴다.
dp1[i] = Math.max(dp1[i-1], dp1[i-2] + money[i]);
}
// (7) 마지막 집은 털지 않고, 지지난 집의 최대금액 계승
dp1[n-1] = dp1[n-2];
// (8)첫번째 집을 털지 않고 두번째 집을 터는 경우
int[] dp2 = new int[n];
// (9)
dp2[1] = money[1];
// (10) 두번째 집만 털거나, 두번째 집을 털지 않고 세번째 집만 털었을때의 가장 큰 금액
dp2[2] = Math.max(money[1], money[2]);
// (11)
for (int i = 3; i < n ; i++) {
dp2[i] = Math.max(dp2[i-1], dp2[i-2] + money[i]);
}
// (12) 두 개의 케이스 중 더 큰 값 리턴
return Math.max(dp1[n-1], dp2[n-1]);
}
}
728x90
반응형
'개발 공부 > 코딩테스트 연습' 카테고리의 다른 글
[프로그래머스 Lv3][자바] 섬 연결하기 (1) | 2024.09.25 |
---|---|
[프로그래머스 Lv3][자바] 가장 먼 노드 (1) | 2024.09.24 |
[프로그래머스 Lv3][자바] 야근 지수 (2) | 2024.09.19 |
[프로그래머스 Lv3][자바] 양과 늑대 (0) | 2024.09.12 |
[프로그래머스 Lv3][자바] 거스름돈 (1) | 2024.09.11 |