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

khy0419 5년 전 0

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

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

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

1
3
5000000
5000000
5000000
는 정상적으로 나옵니다.

2개의 막대를 선택
합 구하기
두개의 차에 대한 절대값이 기존보다 큰 경우 suc배열을 통해 갱신
가능한 경우 flag를 통해 true 반환
가능여부에 따른 출력

#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;
}

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

문제

문제

출처

ICPC

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

khy0419 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말