[SW Expert Academy] 2115. 벌꿀 채취 C/C++ 풀이

이 문제에 꼬박 하루를 썼다면 당신 믿으시겠습니까?

 

애매하게 아는 것은 확실하게 아는 것보다 위험하다는 격언을 생각나게 해주는 문제였습니다... :)

 

문제는 모든 가능성을 이용하는 Brute Force인데, 상자 안의 최대 수익을 구하기 위해 DP(동적 계획법)의 테크닉이 필요하다.

 

동적 계획법은 예전에 포스팅 했으니 참고하세요. (여기로)

동적계획법(1)

 

M개의 영역 안에서 수익의 최댓값을 구하는 것은 반복적으로 사용되기 때문에 cache 배열에 저장해두면 연산을 빠르게 할 수 있다.

 

아래는 풀이

 

#include <stdio.h>
#include <memory.h>
#include <vector>
#include <algorithm>

using namespace std;

//n의 최대는 10
#define N_MAX 10

FILE* in = fopen("input.txt", "r");

int t, n, m, c;
int map[N_MAX][N_MAX];
int cache[N_MAX][N_MAX];
int max_honey;

// m개의 셀 안에서 최대 수익 구하기
// 인자로 시작 x, y 좌표, 얼마나 지나왔는지, 얼마나 많은 벌꿀을 캘 수 있는지, 가격에 대한 정보를 받는다.
int sell_honey(int x, int y, int idx, int cap, int cost) {
	// m개를 지나쳤으면 가격 return
	if (idx >= m)
		return cost;
    // 현재의 벌꿀의 크기가 capacity를 벗어난다면 넘어가고
	if (cap < map[x][y + idx])
		return sell_honey(x, y, idx + 1, cap, cost);
    // 아니면 선택했을 때와 아닐 때의 최댓값을 return
	else
		return max(sell_honey(x, y, idx + 1, cap - map[x][y+idx], cost + (map[x][y + idx] * map[x][y + idx])), sell_honey(x, y, idx + 1, cap, cost));
}

//메모이제이션을 이용하기 위한 함수
int get_honey(int x, int y) {
	if (cache[x][y] != 0)
		return cache[x][y];
	return cache[x][y] = sell_honey(x, y, 0, c, 0);
}

//첫번째 사람이 뽑은 위치가 x, y일 때 최대 벌꿀의 수익 합
void find_honey(int x, int y) {
	// y가 n-m보다 크면 같은 행에서 m개를 선택할 수 없음. 그냥 return.
	if (y > n - m)
		return;
        
    //첫번째 사람이 뽑는 벌꿀 수익의 최대화
	int first = get_honey(x, y);

	//다음 x, y
	int next_x = x, next_y = y;

	//두번째 사람의 벌꿀 최대 수익
	int second = 0;

	while (1 == 1)
	{
    	//next_x와 next_y가 map의 끝에 왔다면 반복문 끝
		if (next_x == n - 1 && next_y == n - 1)
			break;
        //y 증가
		next_y++;
        //근데 y가 n보다 크다면 x에 1을 올리고 y는 0으로 초기화
		if (next_y >= n)
		{
			next_x++;
			next_y = 0;
		}
        // 같은 행인데, 선택하는 영역이 겹친다면 갱신 하지 않음
		if (next_x == x && next_y - y < m)
			continue;
        //next_y 또한 n - m보다 크다면 갱신하지 않음
		if (next_y > n - m)
			continue;
		int tmp = get_honey(next_x, next_y);
        next_x, next_y의 최댓값을 저장
		if(second < tmp)
			second = tmp;
	}
    // 둘의 합의 최댓값 구하기
	if ((first + second) > max_honey)
		max_honey = first + second;
	return;
}


int main() {
	fscanf(in, "%d", &t);
	for (int i = 0; i < t; i++)
	{
		max_honey = 0;
		memset(cache, 0, sizeof(cache));
		fscanf(in, "%d %d %d", &n, &m, &c);
		for(int j = 0; j < n; j++)
			for(int k = 0; k < n; k++)
				fscanf(in, "%d", &map[j][k]);
		for (int j = 0; j < n; j++)
			for (int k = 0; k < n; k++)
				find_honey(j, k);
		printf("#%d %d\n", i + 1, max_honey);
	}

}

sell_honey의 알고리즘을 최댓값으로 정렬 후 차례대로 용량과 비교하며 수익을 뽑는 방식을 이용했는데,

 

그러니 10의 용량일 때, 5 5 7에서 최댓값 정렬 7 5 5 => 7만 뽑아서 수익 냄. 49가 나왔다.

하지만 실제 최댓값은 5 5를 뽑아서 나온 50이다.

 

동적계획법을 빼먹었음...나레기,,