p_완전 범죄_389480

문제

흔적누적시 붙잡힘
A가 가장 누적해서 적게 남기는 경우를 골라라

답

1차답
시간초과 - 점수40점

def solution(info, n, m):
    result = [n]
    hasA = [False]
    def steal(l_n,l_m,start):
        # print(l_n,l_m,start)
        if l_n<=0 or l_m<=0:
            return
        if start>= len(info):
            # print(result)
            hasA[0] = True
            # print(">>",l_n,l_m)
            if result[0] > n - l_n:
                result[0] = n - l_n
            return
        a,b = info[start]
        steal(l_n-a,l_m,start+1)# 왼쪽꺼 훔침
        steal(l_n,l_m-b,start+1) # 오른쪽 꺼 훔침
        # print("----")
    
    steal(n,m,0)
            
    return result[0] if hasA[0] else -1

2차답
5개면
왼왼왼왼왼
오왼왼왼왼
4개의 데이터를
뒤에서부터
(a,b)
dp 2차원 dp일것같긴하다

ai답

def solution(info, n, m):
    # DP 테이블 초기화
    dp = [[[float('inf')] * (m + 1) for _ in range(n + 1)] for _ in range(len(info) + 1)]
    dp[0][0][0] = 0  # 기본 케이스: 물건이 없을 때, 흔적도 없음

    # 각 물건에 대해 반복
    for i in range(1, len(info) + 1):
        a_trace, b_trace = info[i - 1]
        for a in range(n + 1):
            for b in range(m + 1):
                # A가 물건을 훔치는 경우
                if a >= a_trace:
                    dp[i][a][b] = min(dp[i][a][b], dp[i-1][a-a_trace][b] + a_trace)
                # B가 물건을 훔치는 경우
                if b >= b_trace:
                    dp[i][a][b] = min(dp[i][a][b], dp[i-1][a][b-b_trace])

    # A의 최소 흔적 개수 찾기
    min_a_traces = min(dp[len(info)][a][b] for a in range(n) for b in range(m))
    print(dp)

    return min_a_traces if min_a_traces != float('inf') else -1

다른사람 풀이답

def solution(info, n, m):
    INF = 100000
    size = len(info)
    dp = [[INF] * m for _ in range(size + 1)]
    dp[0][0] = 0

    for i in range(1, size + 1):
        a, b = info[i-1]
        for j in range(m):
            # A 선택
            dp[i][j] = min(dp[i][j], dp[i-1][j] + a)
            # B 선택
            if j + b < m:
                dp[i][j + b] = min(dp[i][j + b], dp[i-1][j])

    min_value = min(dp[size])
    return -1 if min_value >= n else min_value