글 읽기 - 3649 로봇 프로젝트 반례 좀 부탁드립니다!

khy0419 5년 전 0

조합으로 푸는걸 연습한다고 한번 해봤습니다.

아래의 방법에 따라 코드를 작성했으며, 현재 50%까지 가고 틀렸습니다가 발생합니다.

반례가 있다면 알려주시면 감사하겠습니다.

테스트 케이스 및
1
3
5000000
5000000
5000000
는 정상적으로 나옵니다.

#define	_CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <math.h>
#include <algorithm>
#include <string.h>

using namespace std;
int N, K; 
int arr[1000001];
int suc[2];

int countBits(int value)
{
	int count = 0;
	while (value > 0)
	{
		if ((value & 1) == 1)
			count++;
		value = value >> 1;
	}
	return count;
}

bool comb()
{
	int ret = -1;
	int tmp[2] = { 0, }; 
	bool flag = false;
	for (int i = 0; i < (1 << K); i++)
	{
		//2개 뽑지 않은 상황이면 패스
		if (countBits(i) != 2) continue;
		int sum = 0, arrayCnt = 0;
		for (int j = 0; j < K; j++)
		{
			if (i&(1 << j))
			{
				//뽑힌 애들에 대해 sum과 tmp배열에 저장
				sum += arr[j];
				tmp[arrayCnt++] = arr[j];
			}
		}
		//구멍의 크기와 맞는지 비교
		if (sum == N)
		{
			//현재 가진 |l1-l2| 보다 더 큰애가 있을때 값 변경
			flag = true;
			if (ret <= abs(tmp[0] - tmp[1]))
			{
				ret = abs(tmp[0] - tmp[1]);
				suc[0] = tmp[0];
				suc[1] = tmp[1];					
			}
		}
	}
	//구멍을 채울 수 있는지
	return flag;
}
int main()
{
	while (scanf("%d", &N) != -1)
	{
		memset(arr, 0, sizeof(arr));
		memset(arr, 0, sizeof(suc));
		N = N * 10000000; //나노미터로 변환
		scanf("%d", &K);
		for (int i = 0; i < K; i++)
			scanf("%d", &arr[i]);
		//2개 뽑는 조합으로 출력
		if (comb() == true)
		{
			sort(suc, suc + 2);
			printf("yes %d %d\n", suc[0], suc[1]);
		}
		else
			printf("danger\n");
	}
	return 0;
}

evenharder 5년 전 1

1 << K는 int형이기 때문에 K가 32만 넘어가도 값이 0이 되어버립니다. long long int로 해도 K가 64만 넘어가면 0이 되어버리고요.

이 점을 고려하지 않고도 K가 10^6까지 갈 수 있다는 걸 생각하면 이 풀이방법은 시간복잡도 O(2^K)가 되기 때문에 너무 느립니다.

모든 조합을 고려하는 풀이를 짜고 싶으시다면 이중 반복문으로 시간복잡도 O(K^2)의 방법을 생각해볼 수 있지만 이 역시 느린 걸 알고 계실 것 같습니다. 꼭 모든 수의 쌍을 고려해야 풀 수 있는 것은 아니므로 이를 고려하여 보다 효율적인 접근을 해보시기 바랍니다.

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

문제

문제

출처

ICPC

3649 로봇 프로젝트 반례 좀 부탁드립니다!

khy0419 5년 전 0

evenharder 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말