오늘 풀어볼 문제는 완전범죄이다!
1. 문제 요약
물건 i를 훔칠 때,
- A도둑이 훔치면 info[i][0]개의 A에 대한 흔적을 남깁니다.
- B도둑이 훔치면 info[i][1]개의 B에 대한 흔적을 남깁니다.
- 각 물건에 대해 A도둑과 B도둑이 남기는 흔적의 개수는 1 이상 3 이하입니다.
경찰에 붙잡히는 조건
- A도둑은 자신이 남긴 흔적의 누적 개수가 n개 이상이면 경찰에 붙잡힙니다.
- B도둑은 자신이 남긴 흔적의 누적 개수가 m개 이상이면 경찰에 붙잡힙니다.
출력 조건
두 도둑 모두 경찰에 붙잡히지 않도록 모든 물건을 훔쳤을 때, A도둑이 남긴 흔적의 누적 개수의 최솟값을 return
2. 나의 접근법
1) B가 훔칠 수 있는 최대 물건을 배낭문제 형식으로 구함
2) 1을 수행하면서, B가 훔친 물건들의 인덱스 번호를 StringBuilder 형식으로 구성
3) B가 m-1의 값을 최대로 훔칠 수 있는 물건을 모두 구했으면, B가 훔친 물건들의 인덱스를 모두 구할 수 있음.
4) 그 후 A는 B가 훔치지 않은 물건들에 대한 본인의 흔적값을 모두 더함. 해당 흔적값이 n 이상이라면 -1 return 그렇지 않다면 흔적값 return
3. 문제 발생 및 해결
현재 방식에서 어려운 점은 B와 A의 가중치가 달라, B가 훔친 물건들의 log를 정확히 기록해놓지 않으면 아무리 B의 최대값을 정확하게 구해도 A의 최소값은 알기 어렵다는 점이었다. 안타깝게도 B의 물건 log를 구현함에 어려움을 느끼게 되었다....
내 접근법이 문제인가 싶었지만, 아무리 생각해도 M-1의 범위에서 B의 최댓값을 구한 후, B가 훔치지 않은 물건들에 대해 A가 가지는 것은 좋은 방법이라고 생각했다.
그리고...이 방법은 해결 가능한 옳은 로직이였다!!!!
바로 배낭 코드를 살짝만 꼬면 아주 쉽게 풀리게 된다.
현재 배낭 코드는 다음과 같이 구성되어 있다.
전형적인 배낭 방법이다.
3.1 배낭 문제 풀이?
배낭문제식 풀이법은 다음과 같다.
1) 바깥 loop에서는 현재 물건의 개수만큼 돈다.
2) 안쪽 loop에서는 B가 가질 수 있는 가중치(여기선 흔적값)만큼의 배열만큼 돈다.
- 그 후 현재 물건을 훔치는 경우와, 훔치지 않는 경우 중 최대값을 dp 배열에 넣는다.
- 현재 가중치(j) 내에서 적립가능한 최대 흔적값을 나타내는 dp[j]
- 현재 가중치(j)에서 현재 흔적값(info[i][1])을 뺀 dp 배열 원소 + 현재 흔적값
❓두 번째 for문에서 index가 0부터 시작하면 안되나요?
안됩니다! 현재 아이템을 사용한 후에 발생하는 변화가 아직 이번 아이템의 사용 여부에 영향을 주지 않도록 하기 위함입니다.
즉 지금 dp 배열은, B의 최대 흔적값을 구해주고 있지만, 이를 A의 최대 절약값으로 바꾸면 문제는 아주 쉽다.
3.2 정답 접근법
dp 배열의 선택지는 다음과 같이 바뀐다.
- B가 해당 물건을 선택해서 “아껴준” A의 흔적의 총합
그렇기 때문에, 가중치 접근은 여전히 B의 가중치로 하고 있지만 실제 배열엔 A의 절약값의 최대치가 들어가고 있다.
아니 조금만 바꿔도 이렇게 쉽다니! 진짜 너무 충격받아서 즐겁게 풀이했다.
4. 정답 코드
import java.io.*;
import java.util.*;
class Solution {
public int solution(int[][] info, int n, int m) {
int answer = 0;
int thingCount=info.length;
int [] dp = new int[m];
int maxATrace = 0;
for(int i=0; i<thingCount; i++){
maxATrace+=info[i][0];
}
for(int i=0; i<thingCount; i++) { //물건개수만큼 바깥 loop
int aTrace = info[i][0];
int bTrace = info[i][1];
for(int j=m-1; j>=bTrace; j--) { //가중치만큼 안쪽 loop
dp[j] = Math.max(dp[j],dp[j-bTrace]+aTrace);
}
}
answer = maxATrace - dp[m-1];
return answer >= n ? -1 : answer;
}
}
엄청나게 빠른 속도로 문제가 풀리는 것을 알 수 있다.
