[Python/파이썬] 백준 20950번 미술가 미미

20950번: 미술가 미미

 

코드

n = int(input())
rgb = [list(map(int, input().split())) for _ in range(n)]
gom_r, gom_g, gom_b = map(int, input().split())

ans = int(1e9)


def bt(idx, r, g, b, k):
    global ans
    if idx >= n:
        return
    # 이번 색 넣음
    mun_r = r+rgb[idx][0]
    mun_g = g+rgb[idx][1]
    mun_b = b+rgb[idx][2]
    diff = abs(mun_r//(k+1)-gom_r)+abs(mun_g//(k+1)-gom_g)+abs(mun_b//(k+1)-gom_b)
    if k+1 >= 2 and ans > diff:
        ans = diff
    if k+1 < 7:
        bt(idx+1, mun_r, mun_g, mun_b, k+1)
    # 이번색 안 넣음
    bt(idx+1, r, g, b, k)
    
    
bt(0, 0, 0, 0, 0)
print(ans)

 

백트래킹을 이용하여 풀이하였다. 색 하나씩 살펴보며 idx번째 물감을 혼합할지 안할지 두가지 경우로 나누어서 재귀적으로 bt 함수를 다시 호출하면 된다. 이때 혼합하는 경우에는 곰두리 값과의 차이를 구해서 그 차이가 ans보다 작은 경우에는 ans 값을 현재의 차이 값으로 바꿔주면 된다.