2115. 벌꿀 채취

static int N, M, C;
static int board[10][10];
static pair<int, int> maximum[10]; //row, value
static int table[10][10];

static int cmp(const void * p1, const void * p2)
{
	int n1 = (*(pair<int, int> *)p1).second;
	int n2 = (*(pair<int, int> *)p2).second;

	return n2 - n1;
}

static void __solution(int * ary, int s, int v, int t, int y, int x)
{
	if (s >= M)
	{
		if (t > table[y][x])
			table[y][x] = t;
			
		if (t > maximum[y].second)
			maximum[y].second = t;
			
		return;
	}

	for (int i = s; i < M; i++)
	{
		int sq = ary[i] * ary[i];
		if (v + ary[i] > C) //C보다 크면 다음으로 넘겨야 함.
			__solution(ary, i + 1, v, t, y, x);
		else
			__solution(ary, i + 1, v + ary[i], t + sq, y, x);
	}
}

static int solution()
{
	int ret, max_col;

	scanf("%d %d %d", &N, &M, &C);
	for (int y = 0; y < N; y++)
	{
		for (int x = 0; x < N; x++)
			scanf("%d", &board[y][x]);
	}

	memset(table, 0, sizeof(table));
	memset(maximum, 0, sizeof(maximum));
	for (int y = 0; y < N; y++)
	{
		maximum[y].first = y;
		for (int x = 0; x + M <= N; x++)
			__solution(board[y] + x, 0, 0, 0, y, x);
	}

	qsort(maximum, N, sizeof(pair<int, int>), cmp);
	ret = maximum[0].second + maximum[1].second; //일단 greedy한 결과를 keep

	max_col = maximum[0].first;
	for (int x = 0; x + M <= N; x++) //처음부터 다시 확인
	{
		for (int x1 = x + M; x1 + M <= N; x1++) //처음에 선택한 것과 겹치지 않게 선택할 수 있다면
		{
			int other = table[max_col][x] + table[max_col][x1];
			if (other> ret) //이 값이 더 크다면
				ret = other;
		}
	}

	return ret;
}

재귀를 이용하여 모든 조합을 만들어야 할 때, 그 종료 조건을 인덱스로 하는 경우가 있다.

특정 조건을 만족 하지 못할 때 해당 인덱스를 스킵하고 넘어가는 경우도 있지만, 

이 문제에서는 해당 값을 선택하여 특정 조건을 만족하지 못하더라도 다음 재귀로 넘어가야 하는데,

이는 해당 값을 스킵하고 나머지 값들을 이용하여 특정 조건을 만족한 뒤, 그 이득을 구하고 최대 값을 갱신해야 하기 때문이다.

 

그리고 최대값을 구하기 때문에 가급적 모든 경우를 체크 가능한 재귀를 이용한 것이다.

 

마지막으로 정리할 부분은 같은 row에서 겹치지 않고 벌꿀을 어떻게 채취 할 것인지에 대한 것이다.

바깥 for문은 A가 선택 하는 것이라 하고, 안쪽 for문은 B가 선택하는 것이라 했을 때,

A입장에서는 x + M <= N, 즉 M만큼의 필드를 확보 할 수 있을때 까지 반복하는 것이고,

이 과정에서 B는

A가 선택한 위치에서 M만큼 떨어진 곳에서 시작을 하여 역시 x1 + M <= N, M만큼의 필드를 확보 할 수 있을 때 까지 반복한다.

 

(ㅁㅁ)(ㅁㅁ)ㅁ

(ㅁㅁ)ㅁ(ㅁㅁ)

ㅁ(ㅁㅁ)(ㅁㅁ)

ㅁㅁ(ㅁㅁ)ㅁ

 

마지막 에서는 굳이 앞에 것을 확인 할 필요가 없다. 첫번째에서 이미 확인을 했기 때문이다.

 

 

//주의사항 및 정리

1. qsort 시 n2 - n1 반환은 내림차순, n1 - n2 반환은 오름차순 이다.

2. 마지막 겹치지 않고 연속적으로 할당하는 방법 외우기.

3. DP를 적용한 방법, 특정 x에서 시작했을 때 최대값만 저장되는 것에 대해서