사이트 #문제: 문제유형 / 난이도

문제 링크 걸기 +

https://school.programmers.co.kr/learn/courses/30/lessons/389480

🔍 Inspection

문제 접근(문제 분석 → 풀이 아이디어)

🚩 FLOW

코드를 풀이할 때 적었던 플로우가 있나요?

1. 누적 흔적이 n(A) , m(B) 가 넘지 않을 것
2. 물건 i 을 훔칠때 남는 흔적 정보 : info[i] = [ A의 흔적 개수 , B의 흔적 개수] info의 len = 물건 개수
3. goal) 모든 물건 훔칠 때 (1) 둘 다 안걸림 => 불가능하면 -1 return (2) 그 중에서 A 의 흔적이" 최소로 남을 경우

dp[i] = [(A선택 시 누적 흔적) , (B 선택시 누적 흔적 )]

점화식 -> i 번 반복 dp[i] = set(dp[i-1][k] + info[i][0] , dp[i-1][k] + info[i][1])

• dp[0] = [(info[i][0],0) ,(0,info[i][1])]
• if dp[i][k][0] >= n or dp[i][k][0] <= m -> skip

3. A의 최소값 return

dp[-1] = sorted(dp[-1])[0]