색상 줄이기

면접 대비

시간 제한1초메모리 제한128 MB

요약

16개의 기준 RGB 색을 읽은 뒤, 이후 입력되는 각 색을 유클리드 거리가 가장 가까운 기준 색에 대응시키고 거리가 같으면 먼저 나온 색을 고른다.

난이도: 쉬움10점 중 2점
유형: 구현, 완전 탐색, 기하, 수학
정답자: 아직 제출이 없습니다

문제

색상 축소(color reduction)는 이산적인 색상 집합을 더 작은 집합으로 대응시키는 사상이다. 이 문제에서는 표준 24비트 RGB 색 공간에서 이러한 대응을 수행한다. 입력으로는 16개의 목표 RGB 색상으로 이루어진 목표 집합과, 그 목표 집합에서 가장 가까운 색으로 대응시킬 임의의 RGB 색상들이 주어진다.

RGB 색상은 순서쌍 $(R, G, B)$ 로 정의되며, 각 성분은 0 이상 255 이하의 정수이다. 두 색상 사이의 거리는 3차원 공간에서의 유클리드 거리로 정의한다. 즉, 두 색상 $(R_1, G_1, B_1)$ 과 $(R_2, G_2, B_2)$ 의 거리 $D$ 는 다음과 같다.

$D = \sqrt{(R_2 - R_1)^2 + (G_2 - G_1)^2 + (B_2 - B_1)^2}$

입력

입력은 RGB 색상들의 목록이며, 한 줄에 하나의 색상이 0 이상 255 이하의 정수 세 개로 주어진다. 각 정수는 공백 하나로 구분된다. 처음 16개의 색상은 목표 집합을 이루고, 나머지 색상들은 이 목표 집합으로 대응된다. 입력은 세 값이 모두 $-1$ 인 줄로 끝난다.

출력

대응시킬 각 색상에 대해, 그 색상과 목표 집합에서 가장 가까운 색상을 (R,G,B) maps to (R2,G2,B2) 형식으로 한 줄에 출력한다. 만약 목표 집합의 두 색상이 똑같이 가깝다면, 목표 집합에서 먼저 나오는 색상을 선택한다.

예제1

예제 1

입력

0 0 0
255 255 255
0 0 1
1 1 1
128 0 0
0 128 0
128 128 0
0 0 128
126 168 9
35 86 34
133 41 193
128 0 128
0 128 128
128 128 128
255 0 0
0 1 0
0 0 0
255 255 255
253 254 255
77 79 134
81 218 0
-1 -1 -1

예상 출력

(0,0,0) maps to (0,0,0)
(255,255,255) maps to (255,255,255)
(253,254,255) maps to (255,255,255)
(77,79,134) maps to (128,128,128)
(81,218,0) maps to (126,168,9)