백준8873 Art Class

작성일 | In

문제 링크

  • http://icpc.me/8873

문제 출처

  • 2013 IOI Day1 2번

풀이

문제를 읽으면 이상한 휴리스틱을 써야한다는 것은 알 수 있습니다.
여러가지 풀이가 있는 것으로 알고 있고, 그 중 한 가지를 소개하고자 합니다.

스타일4(색면회화)에 속한 그림들은 비슷한 색깔들이 큰 덩어리에 뭉쳐있습니다.
스타일1(현대 신조형주의)에 속한 그림들도 비슷한 색깔끼리 뭉쳐있지만 스타일4보다는 덩어리들이 작습니다.
스타일2(인상주의 풍경화)에 속한 그림들은 전체적으로 초록색이 많지만 스타일1/4처럼 거의 같은 색이 덩어리로 뭉쳐있지는 않습니다.
마지막으로 스타일4(표현주의)에 속한 그림들은 무작위에 가깝게 색깔이 칠해져 있습니다.

위 성질을 이용해서 문제를 풀어봅시다.
각 셀마다 인접한 셀과 색깔이 얼마나 차이나는지 계산을 해주고, 적절한 기준을 잡아서 스타일을 분류해주면 됩니다.
인접한 색깔의 차이는 각 채널마다 abs(color[i+1][j] - color[i][j]) 같은 식을 통해 구해줄 수 있습니다.

Green 채널만 봐도 문제를 풀 수 있다고 하는데, 저는 잘 모르겠습니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include "artclass.h"
#include <bits/stdc++.h>
using namespace std;

int style(int h, int w, int r[500][500], int g[500][500], int b[500][500]){
	int sum = 0;
	for(int i=0; i<h-1; i++){
		for(int j=0; j<w-1; j++){
			sum += abs(r[i+1][j] - r[i][j]);
			sum += abs(r[i][j+1] - r[i][j]);
			sum += abs(g[i+1][j] - g[i][j]);
			sum += abs(g[i][j+1] - g[i][j]);
			sum += abs(b[i+1][j] - b[i][j]);
			sum += abs(b[i][j+1] - b[i][j]);
		}
	}
	sum /= h*w*2;
	if(sum < 9) return 4;
	if(sum < 23) return 1;
	if(sum < 54) return 2;
	return 3;
}