[Level 2 | Python] 완전범죄 (완탐 + 더 효율적인 코드)

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

프로그래머스

문제

A도둑이랑 B도둑이 팀을 이루어모든 물건을 훔치려고 하는데, 물건을 훔칠 때마다 각각 흔적을 남긴다. 

흔적이 A,B 각각 n,m이 되면 경찰에게 발각되는데 둘 다 발각되지 않고 A가 최소한으로 흔적을 남기는 경우를 구해야 한다. (A도둑이 B도둑보다 형님인가보다..)

제한 사항

제한사항
1 ≤ info의 길이 ≤ 40
info[i]는 물건 i를 훔칠 때 생기는 흔적의 개수를 나타내며, [A에 대한 흔적 개수, B에 대한 흔적 개수]의 형태입니다.
1 ≤ 흔적 개수 ≤ 3
1 ≤ n ≤ 120
1 ≤ m ≤ 120

풀이 과정

처음에 조합을 통한 완전탐색을 구현했을 때 제한 사항으로 봤을 때 2^40이 걸린다. 아 이거 무조건 DP 문제다 싶었다. 

DP 테이블을 어떻게 만드느냐가 이 문제에 핵심이었던 문제 같다. 

 

dp[i][a][b] 3차원 배열을 통해 문제를 해결했다. 

• dp[i][a][b] : i 번째 물건까지 고려 했을 때 (True / False)
  • A가 a만큼 흔적을 남겼고
  • B가 b만큼 흔적을 남긴 상태로 도달 가능한지 여부

정답은 dp[info의 길이][a][b]가 True인 경우 A의 흔적이 최소인 값을 찾으면 된다. 없으면 -1

 

시간복잡도
O(length * n * m)

 

def solution(info, n, m):
    length = len(info)
    # dp[i][a][b] : info[i] 사용했을 때 a의 누적 흔적, b의 누적 흔적
    dp=[[[False]*m for _ in range(n)] for _ in range(length+1)]
    dp[0][0][0] = True
    
    for i in range(length):
        a_cost, b_cost = info[i]
        for a in range(n):
            for b in range(m):
                if dp[i][a][b]:
                    # a가 훔칠 때
                    na=a+a_cost
                    nb=b
                    if na<n:
                        dp[i+1][na][nb]=True
                    
                    # b가 훔칠 때
                    na=a
                    nb=b+b_cost
                    if nb<m:
                        dp[i+1][na][nb]=True

    answer=-1
    for a in range(n):
        for b in range(m):
            if dp[length][a][b]:
                if answer==-1 or a<answer:
                    answer=a
    return answer

 

더 효율적인 코드 

딕셔너리에 `{A가 남긴 누적 흔적 개수 : B가 남긴 누적 흔적 개수}` 저장해 놓는다. 이전에는 3중 for문으로 다 탐색해서 True인 애들을 찾아내야 했지만 이 방식을 사용하면 dic(딕셔너리)에 담긴 애들만 탐색해주면 된다. 

 

첫번째 test 코드 

info = [[1, 2], [2, 3], [2, 1]]

n=4

m=4

일 때 

A가 훔칠 때, B가 훔칠 때 각각 경우의 수를 tmp에 저장해 놓고 마지막에 dic에 복사해준다.

 

처음에 for문을 돌면

`dic: {1: 0, 0: 2}` A가 훔쳤을 때, B가 훔쳤을 때 경우의 수가 이런 식으로 담긴다. 그 다음에는 `dic: {3: 0, 1: 3, 2: 2}`로 담긴다.

조건들은 

dic 에 가능한 모든 경우의 수에 A가 훔쳤을 때 n보다 작게, B가 훔쳤을 때 m보다 작게 조건을 부여한다. 

tmp 딕셔너리에 없으면 없으니까 바로 tmp에 추가하고 or 같은 A흔적을 가지는 경우, 더 적은 B 흔적을 가지는 값으로 업데이트 해준다.

def solution(info, n, m): 
    dic = {0:0} # 아무것도 안 훔친 초기 상태
    for a,b in info:
        tmp = {}
        for aa, bb in dic.items():
            # A가 훔칠 때
            if aa+a<n:
                if aa+a not in tmp or tmp[aa+a] > bb:
                    tmp[aa+a]=bb
                    
            # B가 훔칠 때
            if bb+b<m:
                if aa not in tmp or tmp[aa] > bb+b:
                    tmp[aa]=bb+b
        if tmp:
            dic=tmp
        else:
            return -1
    return min(dic.keys())