문제풀이/백트래킹
[Python/파이썬] 백준 20950번 미술가 미미
딜레이레이
2024. 2. 24. 14:04
20950번: 미술가 미미
미미는 미적 감각이 뛰어난 미술가이다. 미미는 때때로 여러 물감을 섞어 새로운 색의 물감을 만들고는 한다. 어느 날 그림을 그리던 미미는 놀라 자빠질 수밖에 없었다. 미미가 가장 아끼는 곰
www.acmicpc.net
코드
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 값을 현재의 차이 값으로 바꿔주면 된다.