문제 설명
A도둑과 B도둑이 팀을 이루어 모든 물건을 훔치려고 합니다. 단, 각 도둑이 물건을 훔칠 때 남기는 흔적이 누적되면 경찰에 붙잡히기 때문에, 두 도둑 중 누구도 경찰에 붙잡히지 않도록 흔적을 최소화해야 합니다.
물건을 훔칠 때 조건은 아래와 같습니다.
- 물건 i를 훔칠 때,
- A도둑이 훔치면 info[i][0]개의 A에 대한 흔적을 남깁니다.
- B도둑이 훔치면 info[i][1]개의 B에 대한 흔적을 남깁니다.
- 각 물건에 대해 A도둑과 B도둑이 남기는 흔적의 개수는 1 이상 3 이하입니다.
경찰에 붙잡히는 조건은 아래와 같습니다.
- A도둑은 자신이 남긴 흔적의 누적 개수가 n개 이상이면 경찰에 붙잡힙니다.
- B도둑은 자신이 남긴 흔적의 누적 개수가 m개 이상이면 경찰에 붙잡힙니다.
각 물건을 훔칠 때 생기는 흔적에 대한 정보를 담은 2차원 정수 배열 info, A도둑이 경찰에 붙잡히는 최소 흔적 개수를 나타내는 정수 n, B도둑이 경찰에 붙잡히는 최소 흔적 개수를 나타내는 정수 m이 매개변수로 주어집니다. 두 도둑 모두 경찰에 붙잡히지 않도록 모든 물건을 훔쳤을 때, A도둑이 남긴 흔적의 누적 개수의 최솟값을 return 하도록 solution 함수를 완성해 주세요. 만약 어떠한 방법으로도 두 도둑 모두 경찰에 붙잡히지 않게 할 수 없다면 -1을 return해 주세요.
브레인스토밍
- 물건 i에 대해서 A든 B든 훔치는 사건은 무조건 발생한다
- 그렇다면 조건을 만족하는 경우가 몇가지 존재하는 것 같다
- 물건에 대한 완전 탐색을 하지만 조건을 만족하면서 최소인 것을 정답으로 갖는다
- 경우의 수는 로 상당히 커진다
- 따라서 위처럼 중복이 되는 경우는 아예 고려하지 않는 방법 필요
- 메모 방법(j번째 물건)
- (A=4, B=3), (A=2, B=3)와 같은 상황에서는 후자만 기억하면 될 것이다
- 각 물건에 대해 조건을 만족하고 최소인 A만 고려해서 기록해두면 될 것이다
제한사항
- 1 info 의 길이 40
- info[i] 는 물건 i를 훔칠 때 생기는 흔적의 개수를 나타내며, [A에 대한 흔적 개수, B에 대한 흔적 개수]의 형태
- 1 흔적 개수 3
- 1 n 120
- 1 m 120
브레인스토밍
- info, n, m 모두 작은 숫자임
- 모든 경우를 고려한다면 2의 지수 형태로 커지므로 보다 효과적인 방법 필요
Python
- 시간 복잡도:
- x는 물건의 총 개수(length of info)
- 각 물건에 대해 길이 m의 dp를 순환
- 공간 복잡도: O(m)
- B의 최대 흔적 개수 만큼 dp 생성(m)
def solution(info, n, m):
# dp의 index: b의 흔적, value는 최소 a
INF = 10**9
dp = [INF] * m
dp[0] = 0 # 최초에 a, b 모두 0
# i번째 물건에 대해 dp를 갱신하는 구조
# O(len(info)*m): 40 *120이 최대
for a, b in info:
new_dp = [INF] * m
for b_sum in range(m):
# 0. 이전에 기록이 없음
a_sum = dp[b_sum]
if a_sum == INF:
continue
# 1. A가 훔침 -> A갱신, B그대로 -> 더 작으면 A갱신
a_new = a_sum + a
if a_new < n and a_new < new_dp[b_sum]:
new_dp[b_sum] = a_new
# 2. B가 훔침 -> A그대로, B갱신 -> 더 작으면 A갱신
b_new = b_sum + b
if b_new < m and a_sum < new_dp[b_new]:
new_dp[b_new] = a_sum
# i번째 물건에 대한 dp 갱신
dp = new_dp
# 최소 a가 정답!
ans = min(dp)
if ans == INF:
ans = -1
return ans