[백준/Python] 20950번 : 미술가 미미

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

문제 분석

분류

• 브루트포스 알고리즘
• 백트래

문제 설명

미미는 미적 감각이 뛰어난 미술가이다. 미미는 때때로 여러 물감을 섞어 새로운 색의 물감을 만들고는 한다. 어느 날 그림을 그리던 미미는 놀라 자빠질 수밖에 없었다. 미미가 가장 아끼는 곰두리색 물감이 다 떨어졌기 때문이다. 하지만 미미는 새 물감을 살 돈이 없다. 물감은 역시 섞어 써야 제맛이다. 미미는 남은 물감들을 섞어 곰두리색 물감을 만들기로 결심하였다.

먼저 RGB 표기법에 대하여 알아보자. RGB 표기법은 빨간색(Red), 초록색(Green), 파란색(Blue)을 혼합하여 색을 나타내는 방법으로, 각각의 색은 밝기에 따라 0부터 255까지의 정수로 표현한다. 예를 들어, 분홍색은 rgb(255, 192, 203)과 같이 표현한다. 이는 빨간색을 255만큼, 초록색을 192만큼, 파란색을 203만큼 혼합하였다는 의미이다.

새로운 물감을 만들기 위해서는 남아 있는 물감 중 혼합할 물감들을 선택한 후 이들을 동일한 비율로 섞는다. P1, P2, ..., PK번 물감을 섞어 새로 만들어지는 색은 RGB 표기법으로 다음과 같다.

즉, 새로운 R 값은 혼합할 모든 물감의 R 값을 더한 후 이를 물감의 개수로 나누어 구한다. 이때 소수점은 버린다. G와 B 값도 동일한 방법으로 구한다.

색 i와 색 j의 차이는 다음과 같다.

물감들을 섞어서 만들 수 있는 색 중 곰두리색에 가장 가까운, 즉 곰두리색과의 차이가 가장 작은 색을 문두리색이라고 한다. N개의 물감과 곰두리색이 주어졌을 때, 곰두리색과 문두리색의 차이를 구하는 프로그램을 작성하시오. 단, 미미는 아직 실력이 부족하여 최대 7개의 색만을 혼합할 수 있다. 또한 물감을 섞지 않고 단독으로 사용할 수 없다.

입력

첫 번째 줄에 물감의 개수 N이 주어진다.

이후 N개의 줄 중 i(1 ≤ i ≤ N)번째 줄에는 i번 물감의 Ri, Gi, Bi 값이 주어진다.

다음 줄에 곰두리색의 Rg, Gg, Bg 값이 주어진다.

모든 입력은 정수이며 공백으로 구분되어 주어진다.

출력

첫 번째 줄에 곰두리색과 문두리색의 차이를 출력한다.

소스코드

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 값을 현재의 차이 값으로 바꿔주면 된다.