글 읽기 - 문제에서 원하는 것을 모르겠습니다.

nikemaniya 8년 전 0

문제에서 출력하라는 값이, 주어진 박스 중에서

가장 큰 박스에 크기 순서별로(중복 없이) 들어갈 수 있는 박스 개수 아닌가요?

코드가 틀렸다고 합니다.

저는 일단,

1) 박스 크기를 내림차순으로 정렬

2) 가장 큰 박스 box[0] 를 max 값으로 설정 및 해당 크기의 박스는 사용된 박스로 check

3) 전체 박스 돌면서 사용안된 박스 중에서 max 보다 작은 박스가 있을 경우 cnt++

틀린 코드 부분이 어느 곳인지 찾지 못하겠습니다.

일단, 문제 이해가 정확하다고 확신이 안 들어서요.

성공 하신 분들의 답변에 미리 감사드립니다.

#include <stdio.h>

#define MAX_NUM 1000

int n;
int box[MAX_NUM] = { -1, };
int buf[MAX_NUM] = { -1, };
bool check[MAX_NUM] = { false, };
int cnt = 0;
int max = 0;

inline void swap(int *a, int *b)
{
	int temp = *a;
	*a = *b;
	*b = temp;
}

void merge(int start, int mid, int end, int order)
{
	int i = 0;
	int first_p = start;
	int second_p = mid + 1;

	for (i = 0; (first_p <= mid) && (second_p <= end); i++)
	{
		if (((box[first_p] > box[second_p]) && (order == 1)) || ((box[first_p] < box[second_p]) && (order == 0)))
			buf[i] = box[first_p++];
		else
			buf[i] = box[second_p++];
	}

	while (first_p <= mid) buf[i++] = box[first_p++];
	while (second_p <= end) buf[i++] = box[second_p++];

	for (i = 0; i < (end - start) + 1; i++)
	{
		box[i + start] = buf[i];
	}
}

void sort(int start, int end, int order)
{
	if (start == end)
		return;
	else if (end - start == 1)
	{
		if (((box[start] > box[end]) && (order == 0)) || ((box[start] < box[end]) && (order == 1)))
			swap(&box[start], &box[end]);
	}
	else
	{
		int mid = (start + end) / 2;
		sort(start, mid, order);
		sort(mid + 1, end, order);
		merge(start, mid, end, order);
	}
}

bool verify(int x)
{
	if (check[x])
		return true;

	return false;
}

void comp()
{
	for (int i = 0; i < n; i++) {
		if (!verify(box[i])) {
			if (box[i] < max) {
				max = box[i];
				cnt++;
			}
			check[box[i]] = true;
		}
	}

	printf("%d\n", cnt);
}

int main()
{
	scanf("%d", &n);

	for (int i = 0; i < n; i++)
		scanf("%d", &box[i]);

	sort(0, n - 1, 1);
	max = box[0];
	check[box[0]] = true;

	comp();

	return 0;
}

chatterboy 8년 전 1

저는 dynamic programming에서 LIS(longest Increasing Subseqeunce)를 사용해서 풀었어요~

sksdong1 8년 전 1

박스가 놓인 순서를 바꾸면 안됩니다

주어진 숫자(박스)들의 순서를 바꾸지 않고 부분적으로 가장 긴 증가 수열을 찾으면 됩니다

nikemaniya 8년 전 0

감사합니다. 박스 순서를 멋대로 바꿔버렸네요 ㅎㅎ

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

문제

문제

출처

ICPC

문제에서 원하는 것을 모르겠습니다.

nikemaniya 8년 전 0

chatterboy 8년 전 1

sksdong1 8년 전 1

nikemaniya 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말