백준 : 20950 미술가 미미 [실버2, 파이썬, 백트래킹]

문제

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

먼저 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 값이 주어진다.

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

출력

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

제한

• 2 ≤ N ≤ 30
• 0 ≤ Ri, Gi, Bi ≤ 255
• 0 ≤ Rg, Gg, Bg ≤ 255

예제 입력 

3
255 0 0
0 255 0
0 0 255
64 64 64

예제 출력

63

문두리색은 rgb(85, 85, 85)이다.

예제 입력 

2
255 255 255
255 130 151
255 255 255

예제 출력 

115

문두리색은 rgb(255, 192, 203)이다.

 

[문제 해석]

1. R,G,B로 구성된 물감 N개가 주어지고, 마지막줄에 곰두리색 RGB를 준다.

2. 주어진 N개의 R, G, B 각각 서로 더해준다.
3.더한 값을 N으로 나누면 문두리색 RGB가 나온다.

4. 마지막 줄에 주어진 곰두리색과 구한 문두리색의 차를 출력한다.

 

 

[코드 풀이]

# 백트래킹
def go(x, num):
    global ans, new_R, new_G, new_B # 전역변수로 선언한다.
    
    if num >= 2: # 물감 한가지 색만 가지고 섞을 수 없으니까 2부터 차이값을 구한다.
    	# ans가 계속 업데이트 되기때문에 min() 활용한다.
        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)] # 기본 입력 : RGB 배열
R, G, B = map(int, input().split()) # 기본 입력 : 곰두리 RGB
new_R, new_G, new_B = 0, 0, 0 # 계산한 문두리 RGB 넣을 변수
ans = 987654321 # 출력할 변수 : 곰두리와 문두리 값 차이 들어갈 변수
go(-1, 0) # 백트래킹 함수 호출
print(ans) # 출력

- 색이 섞어지는 모든 경우의 수를 고려해야한다. 

- N이 30까지이기때문에 백트래킹 적용이 가능하다.