[BOJ 20950, Python 3] 미술가 미미

https://www.acmicpc.net/problem/20950

20950번: 미술가 미미

 

풀이

문제를 읽어보면 색을 섞을 수 있는 모든 경우의 수를 확인해야한다는 것을 알 수 있습니다. 이러면 알고리즘 범위가 좀 좁혀지고, 거기다가 N의 값이 30이라 작기 때문에 바로 백트래킹을 생각해냈습니다.

근데 백트래킹을 너무 오랜만에 풀어서 그런지 구현에서 자꾸 틀려서 좀 고생했네요

 

문제에서 색깔 하나만 사용할 수는 없기 때문에 그 부분을 유의해서 백트래킹을 구현해주면 됩니다.

 

 

코드

def go(x, num):
    global ans, new_R, new_G, new_B
    if num >= 2: ans = min(ans, abs(new_R // num - R) + abs(new_G // num - G) + abs(new_B // num - B))
    for i in range(x+1, n):
        new_R, new_G, new_B = new_R + arr[i][0], new_G + arr[i][1], new_B + arr[i][2]
        if num < 7: go(i, num + 1)
        new_R, new_G, new_B = new_R - arr[i][0], new_G - arr[i][1], new_B - arr[i][2]
 
n = int(input())
arr = [[*map(int, input().split())] for _ in range(n)]
R, G, B = map(int, input().split())
new_R, new_G, new_B = 0, 0, 0
ans = 987654321
go(-1, 0)
print(ans)