[프로그래머스] 도둑
https://school.programmers.co.kr/learn/courses/30/lessons/42897
문제
도둑이 어느 마을을 털 계획을 하고 있습니다. 이 마을의 모든 집들은 동그란 형태로 배치되어 있다.
각 집들은 서로 인접한 집들과 방범장치가 연결되어 있어 인접한 두 집을 연속으로 털면 경보가 울린다.
각 집에 있는 돈이 담긴 배열 money가 주어질 때, 도둑이 훔칠 수 있는 돈의 최댓값을 return 하는 메서드를 작성하라.
나의 답안
몇 시간을 헤맨 끝에 겨우 풀었다.
아래 코드들처럼 이것저것 시도해 보았으나 테스트케이스 및 효율성 검사에서 탈락.
첫 번째 코드(오답)
import java.util.*;
class Solution {
public int[] solution(int[] arr, int[] query) {
int[] dp = new int[money.length];
dp[0] = money[0];
dp[1] = Math.max(money[0], money[1]);
for (int i=2; i<money.length; i++) {
dp[i] = Math.max(money[i]+dp[i-2], dp[i-1]);
}
int answer = dp[dp.length-1];
return answer;
}
}
- n번째 집을 터는 경우와 털지 않는 경우 둘로 나누어 더 큰 값을 dp(n)의 값으로 결정하는 방법.
집이 원형으로 배치되어 있다는 것을 망각하고 풀었다.
따라서 맨 앞의 값과 뒤의 값을 둘 다 터는 경우가 발생하므로 오답이다.
두 번째 코드(오답)
class Solution {
public int solution(int[] money) {
int evenSum = 0, oddSum = 0;
for (int i = 0; i < money.length; i++) {
if (i % 2 == 0) {
evenSum += money[i];
System.out.println("evenSum :"+evenSum);
} else {
oddSum += money[i];
System.out.println("oddSum :"+oddSum);
}
}
if (money.length % 2 == 1) {
evenSum -= Math.min(money[0], money[money.length - 1]);
}
return Math.max(evenSum, oddSum);
}
- 한 칸 건너뛰면서 더하는 거니까, 홀수 인덱스 값들의 합과 짝수 인덱스 값들의 합을 비교하면 되겠네? 생각하고 작성.
꼭 한 칸씩만 건너뛰면서 더해야 최대가 되는 것은 아니다. 예를 들어,
[1000, 1, 1, 1000, 2] 의 경우 2000이 최댓값이지만, 위의 코드대로 수행하면 1003이 반환될 것이다.
세 번째 코드(오답)
class Solution {
public int solution(int[] money) {
int[] dp1 = new int[money.length];
int[] dp2 = new int[money.length];
dp1[0] = money[0];
dp1[1] = Math.max(money[0], money[1]);
dp2[money.length-1] = money [money.length-1];
dp2[money.length-2] = Math.max(money[0], money[1]);
int idx2 = money.length-3;
for (int i=2; i<money.length-1; i++) {
dp1[i] = Math.max(money[i]+dp![i-2], dp1[i-1]);
dp2[idx2] = Math.max(money[idx2]+dp2[idx_r+2], dp2[idx_r+1]);
idx2--;
}
return Math.max(dp1[money.length-2], dp2[1]);
}
- 맨 앞과 뒤를 연속해서 털지 않도록 dp1과 dp2로 나누어
dp1은 앞에서부터 n-1번째 값까지, dp2는 n번째 값부터 2번째 값까지 최댓값을 구하는 코드를 작성했다.
이건 사실 왜 오답인지 아직도 모르겠다. 예외 케이스가 무엇인지 알려주실 선배님들 부탁드립니다..
모범 답안
- 원형으로 되어있으므로 맨 앞집을 터는 경우와 털지 않는 경우로 나누어 dp1, dp2로 각각 분류
- dp1에서는 맨 앞집부터 맨 끝집 직전 집까지 털 경우의 최대값을 구함
- dp2에서는 두 번째 집부터 맨 끝집까지 털 경우의 최대값을 구함
- dp1, dp2 중 최대값을 반환
class Solution {
public int solution(int[] money) {
int[] dp1 = new int[money.length];
int[] dp2 = new int[money.length];
dp1[0] = money[0];
dp1[1] = Math.max(money[0], money[1]);
dp2[0] = money[1];
dp2[1] = Math.max(money[1], money[2]);
for (int i = 2; i < money.length - 1; i++) {
dp1[i] = Math.max(money[i] + dp1[i - 2], dp1[i - 1]);
dp2[i] = Math.max(money[i+1] + dp2[i - 2], dp2[i - 1]);
}
return Math.max(dp1[money.length - 2], dp2[money.length - 2]);
}
}
저녁시간 내내 이것만 고민하다가 끝났지만, 어느 정도 모범답안에 가까운 답을 도출해서 아주 뿌듯했다..
점점 발전하고 있는 것이 보인다!