글 읽기 - 가슴이 아프고 먹먹합니다 ㅠㅠ

qwe1234567 6년 전 0

예제도 똑바로 나오고 2 ~ 3번정도 다시짰는데 안나오네요.

Backtracking 으로 모든 경우를 다 탐색해 봤습니다. inc 배열로 특정 소의 포함 여부를 정하고 BT() 함수로 inc 배열의 가능한 모든 조함을 짠 다음에 포함된 소에 대해서만 조합이 가능한지 알아내고 불가능하면 return 아니면 toth 하고 sf(답) 을 동기화 켰습니다.

#include<stdio.h>
#include<algorithm>
using namespace std;
long long int N, H;
struct cow {
	long long int w, s, h;
};
cow list[30] = { 0 };
bool op(cow a, cow b);
bool inc[30] = { 0 };
void BT(int idx);
long long int totw = 0, toth = 0, sf = -1;
int main()
{
	scanf("%lld%lld", &N, &H);
	for (int i = 0; i < N; i++)
	{
		scanf("%lld%lld%lld", &list[i].h, &list[i].w, &list[i].s);
	}

	sort(list, list + N, op);

	BT(0);

	if (toth < H) {
		printf("Mark is too tall");
	}

	else {
		printf("%lld", sf);
	}


	return 0;
}

bool op(cow a, cow b)
{
	if (a.s >= b.s) return false;
	else return true;
}

void BT(int idx)
{
	if (idx == N)
	{
		long long int tw = 0, th = 0, tsf = 2147483647;
		for (int i = 0; i < N; i++)
		{
			if (inc[i]) {
				if (tw > list[i].s) return;
				else {
					if (list[i].s - tw < tsf) tsf = list[i].s - tw;
					tw += list[i].w;
					th += list[i].h;
				}
			}
		}
		if (th >= H&&sf < tsf) toth = H, sf = tsf;
		return;
	}
	else
	{
		BT(idx + 1);
		inc[idx] = !inc[idx];
		BT(idx + 1);
		inc[idx] = !inc[idx];
	}
}

QuqqU 6년 전 0

최소한 어떻게 짰는지 상세한 설명과 주석이 있었으면 좋겠습니다!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

가슴이 아프고 먹먹합니다 ㅠㅠ

qwe1234567 6년 전 0

QuqqU 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말